4

合計は何にO(1)+O(2)+ .... +O(n)評価されますか?

私はそれが書かれたどこかでその解決策を見ました:

O(n(n+1) / 2) = O(n^2)

しかし、私はそれに満足してO(1) = O(2) = constantいませんO(n)。私はコーメンでもこれを見ました：

Σ(i=1 to n) O(i)

上記の式には、無名関数が 1 つしかありません。O(1) + O(2) + ... + O(n)この関数は、実際には明確な解釈がない関数と同じ ではありません。

4

4 に答える 4

4

タグasymptotic_complexityがあるため、質問は完全に話題になっているようです...

CLRSによると、p。49,

「式中の無名関数の数は、漸近記法が現れる回数に等しいと理解されています。たとえば、式では

sum(O(i), i=1..n)

無名関数 (i の関数) は 1 つだけです。したがって、この式は O(1) + O(2) + ... + O(n) と同じではなく、実際には明確な解釈がありません。」

実際、数式では、「O」表記の背後にある定数はすべて異なる場合があり、それらの増加により、合計全体の漸近動作が変わる場合があります。これを書かないでください！

sum(O(i), i=1..n) でより完全に質問に答えるには、次の事実を使用できます (以下についてはGKP p. 450 を参照)。

O(f(n)g(n)) = f(n) O(g(n))

したがって、O(i) = i O(1)、今回は式に同じ O(1) を使用します。したがって、

sum(O(i), i=1..n) = sum(i, i=1, n) O(1)

=n(n+1)/2 O(1) = O(n^2)

このようにして、問題なく合計を削除できます。

于 2013-09-12T07:40:34.440 に答える
2

Big-Oh表記の定義に従います。

n関数がf_iあり、それぞれが満たす

a_i * i <= f_i(x) <= b_i * i; x > X_i

いくつかの正の定数に対してa_i, b_i、十分に大きいX_iです。不等式をX = max_i ( X_i )合計して取得しますn

sum_i=1..n ( a_i * i ) <= sum_i=1..n ( f_i(x) ) <= sum_i=1..n ( b_i * i )

注意して

sum_i=1..n ( min(a_i) * i ) <= sum_i=1..n ( a_i * i )
sum_i=1..n ( b_i * i )      <= sum_i=1..n ( max(b_i) * i )

に到着

    min(a_i) * 0.5*(n(n-1))  <= sum_i=1..n ( f_i(x) ) <= max(b_i) * 0.5*(n(n-1))
<=>       A       * (n(n-1)) <= sum_i=1..n ( f_i(x) ) <=        B      *(n(n-1))

したがって、開始した関数の合計は確かにO(n^2)です。

于 2013-09-12T07:39:12.097 に答える
0

式を見つけるにはコツがありますが、実際にはそれほど難しくありません。

あなたが持っている: 1 + 2 + 3 + 4 + .... + n

リストを 2 回数えると (1 回は低から高に、もう 1 回は高から低に並べると、2 倍の結果が得られます)。

((1 + 2 + 3 + 4 + ... + n) + (n + (n - 1) + (n - 2) ... + 2 + 1)) / 2

これは

((1 + n) + (2 + n - 1) + (3 + n - 2) + ... + (n + 1)) / 2

そしてこれは：

((n + 1) * n) / 2

または、o 概念 O(n²) で正しいように。

于 2013-09-12T13:34:36.193 に答える
0

確かに、O(1) と O(2) は定数なので、忘れて構いません。しかし、O(n/2) は定数ですか、いいえだと思います。だから（宿題のために）要素の後半だけを数えてみてください：

O(n/2) + O(n/2+1) + ... O(n) = ??

あなたが思いつくでしょうO(n^2):)

于 2013-09-12T07:22:16.443 に答える