0

次のセグメントの Big O の複雑さを計算する方法を説明してください。

i := n;
while i > 1 do
  begin
    for j:= i div 2 + 1 to i do
      begin
        k := 2;
        while n >= k do
          k := k * k
      end;
    i := i div 2
  end;

(Pascal ですが、ここでは言語はあまり重要ではありません。) 正解は ですがn*log(log(n))、そこにたどり着く方法がわかりません。

4

1 に答える 1

2

内側のループから始めます。

    k := 2;
    while n >= k do
      k := k * k

これは、 に達するまで値 2、2 2、2 4、2 8、.. を割り当てます。これは O(log(log(n)) です。反復回数 m を呼び出すと、まで反復されるためです。kn

2 2 m > n → log(2 2 m ) > log(n) → log(log(2 2 m )) > log(log(n)) →

→ m > log(log(n)) → m = log(log(n)) + 1

それで

for j:= i div 2 + 1 to i do
  begin
    //O(log(log(n))
  end;

これには i / 2 回の反復があるため、O( (i / 2) log(log(n)))

i := n;
while i > 1 do
  begin
    // (i / 2) log(log(n))
    i := i div 2
  end;

これには、合計される O( (i / 2) log(log(n))) の O(log(n)) 回の反復があります。 

  O( (n/2) log(log(n)) + (n/4) log(log(n)) + (n/8) log(log(n)) + (n/16) log(log( n)) + ... ) =
= O( (1/2 + 1/4 + 1/8 + 1/16 + ...) n ログ (ログ (n)) ) =
= O( 0.1111111…<sub>2 n log(log(n)) ) =
= O( n log(log(n)) )

(0.11111…<sub>2 = 1、0.999…<sub>10 = 1 と同じですが、とにかく O() では関係ありません)

于 2012-12-28T11:19:25.660 に答える