- Swift part4 [転載禁止]©2ch.net
33 ：デフォルトの名無しさん[sage]：2014/11/20(木) 12:31:23.88 ID:SrHOb8b0 - いや普通の人は普通にStack Overflow にお世話になるから
|
- 関数型プログラミング言語Haskell Part26
539 ：デフォルトの名無しさん[sage]：2014/11/20(木) 18:11:13.19 ID:SrHOb8b0 - T(n) = 2T(n/2) + O(n)
T(n) = 2T(n/2) + a * n.
U(n) = T(2^n) とおく。log を 2 を底とする対数関数として、
T(n) = U(log n) = 2T(n/2) + a * n = 2U(log n - 1) + a * n.
N = log n とおくと、
U(N) = 2U(N-1) + a * 2^N.
両辺を 2^N で割ると
U(N)/2^N = U(N-1)/2^(N-1) + a.
よって、
U(N)/2^N = a N.
i.e. U(N) = a N * 2 ^ N.
N = log n. U(N) = T(n) より、
T(n) = a log n * n = O(n log n).
高校レベルの知識で解いたらこうなった
|
- C++14/C++1z 20
59 ：デフォルトの名無しさん[sage]：2014/11/20(木) 18:15:07.02 ID:SrHOb8b0 - constexpr がコンパイル時エラーとか返せると良いのだが。
ダメな引数を与えられたときとかに。
|
- 関数型プログラミング言語Haskell Part26
541 ：デフォルトの名無しさん[sage]：2014/11/20(木) 19:16:13.26 ID:SrHOb8b0 - > 上の証明でいうとO(n)をa*nで置き換えるのがまだ解ってない。
見通しが良いからそう変えただけで、別にそこは置き換えなくても無問題だが。
|
- 関数型プログラミング言語Haskell Part26
543 ：デフォルトの名無しさん[]：2014/11/20(木) 22:30:20.76 ID:SrHOb8b0 - >>542
O(1) 以外の何物でもない
|