1

Big O の複雑さを計算する必要がある 2 つの別個のコードがあります。最初のものは次のとおりです。

k:=1;
s := 4;
while k < N do
begin
    k := 2 * k;
    m:=1;
    while m < N do
    begin
       for i := m to 2*m-1 do s := s + 2;
       m := m + m;
    end;
end;

正解は N*log(N) です。2 番目のコードは次のとおりです。

m:=1;
FOR i:=n downto 1 do
BEGIN
  m:=m*2;
  y:=i MOD 2;
  x:=m;
  WHILE x>y DO
  BEGIN
     x:=x DIV 2;
     y:=y*2
 END    
END

2 番目の正解は n*n です。私は数学を正しく理解できないようです。どちらか一つでもご協力いただければ大変助かります。

4

1 に答える 1

0

この最初のコードを見てみましょう。

k := 1;
s := 4;
while k < N do
begin
    k := 2 * k;
    m := 1;
    while m < N do
    begin
       for i := m to 2*m-1 do s := s + 2;
       m := m + m;
    end;
end;

注意すべきことの 1 つは、内部ループと外部ループが互いに完全に独立しているため、個別に分析できることです。内側のループから始めましょう。

このループが実行mされると、反復ごとに m が 2 倍になるため、取得される値は 1、2、4、8、16、32 などになります。ループ内には、合計 m 回実行される 3 番目の小さなループがあります。これは、外側のループが k 回実行される場合、ループの合計実行時間は次の式で与えられることを意味します。

1 + 2 + 4 + 8 + ... + 2 k

注意すべきことの 1 つは、内側のループがm≥になるとすぐに終了することNです。反復kでは の値mは 2 kであるため、ループは 2 k ≥になるとすぐに実行を停止しますN。これは、k が少なくとも log 2 N になるとすぐに発生します。したがって、ループは最大で log 2 N 回実行されるため、ここで行われる合計作業は次のようになります。

1 + 2 + 4 + 8 + ... + 2 lg N = 2 lg N + 1 - 1 = 2N - 1

ここでは、等比級数の和の式を使用して和を単純化しています。これは、ループ本体の各反復が Θ(N) の作業を行うことを意味します。

あとは、外側のループが何回実行されるかを計算するだけです。内側のループと同様に、外側のループは反復ごとに 2 倍になる変数 (つまりk) によって制御されることに注意してください。同様のロジックを使用すると、このループは Θ(log N) 回実行されるため、合計実行時間は Θ(N log N) になります。

要点:

役立つヒント #1:反復ごとにサイズが 2 倍になり、変数が制限 N に達すると停止する変数によって制御されるループは、O(log N) 回実行されます。

役立つヒント #2: 1 + 2 + 4 + ... + 2 k = 2 k+1 - 1

では、2 番目のコードを見てみましょう。

m := 1;
FOR i := n downto 1 do
BEGIN
  m := m * 2;
  y := i MOD 2;
  x := m;
  WHILE x > y DO
  BEGIN
     x := x DIV 2;
     y := y*2
 END    
END

m前と同様に、変数は各反復で 2 倍になり続けることに注意してください。m の値は 1, 2, 4, 8, 16, 32, 64 などになるため、これはおそらく注目に値するでしょう。より一般的には、反復iでmは の値は 2 iになります。

では、内側のループがどの程度の作業を行うかを見てみましょう。xが の値で始まることに注意してください。mこれは 2 iです。ループの反復ごとに、x は 2 分の 1 に減少します。これは、このループの最大反復回数が log m = log 2 i =であることを意味しますi。これは、ほとんどの場合、内側のループが常に実行されることを意味するため、確かに気の利いたものiです。

それができたら、ランタイムを決定することはそれほど難しくありません。i は N から 0 までカウントダウンするため、実行される作業の合計は最大で

n + (n - 1) + (n - 2) + ... + 2 + 1 = O(n 2 )

したがって、実行時間は O(n 2 ) です。

お役に立てれば！

于 2013-10-27T00:13:46.707 に答える