2

私は大きな問題でいくつかの課題を抱えています。これらは宿題ではありません。ここで概念をよりよく理解するために、これらの問題を書いています。

function func(n)
{
     int k,i = 0;
     while(k < n){ < --- Guessing this outer loop is O(n/2)
        k = n + 2
        i = 0;
        while(i < k){ <--- Not sure what this is?
            i ++;
            i = i * i;
         }
      }         
}

内側のループで何が起こっているのか、そしてあなたのロジックがどのようにして最終的に大きな表記にたどり着くのかを説明していただければ幸いです。

4

3 に答える 3

4

テスト(k < n)とステップを含む外側のループはk = n + 21 回実行され、O(1) 倍の複雑さを提供します。

内側のループにはテスト(i < k)、つまり があり 、最後に(i < n+2)ステップがあります。i++; i=i*i;

i = (...(((1+1)^2+1)^2+1)^2+ ... )^2 > n+2`

i超指数関数的な値になります。つまりi、p パスで exp(exp(p)) よりも速く成長するため、全体的な複雑さは O(log log n) よりも小さくなります。これは、前述の O(log n) よりも厳密な境界です。これも上限ですが、それほど厳密ではありません。

于 2012-10-30T17:15:34.050 に答える
2

@alestanis は、コメントよりもはるかに正確なこの問題の分析のように見えるものを提供してくれましたが、それでも完全に正しいとは思いません。

i内側のループによって生成されたの値を出力する小さなテスト プログラムを作成しましょう。

#include <iostream>

void inner(double k) {
    double i;

    i = 0.0;
    while(i < k) {
        i ++;
        i = i * i;
        std::cout << i << "\n";
     }
}

int main() {
    inner(1e200);
    return 0;
}

これを実行すると、次の結果が得られます。

1
4
25
676
458329
2.10066e+011
4.41279e+022
1.94727e+045
3.79186e+090
1.43782e+181
1.#INF

反復回数が対数である場合、特定の数に到達するための反復回数は、制限内の桁数に比例する必要があります。たとえば、対数の場合、1e181 に到達するには約 180 回の反復が必要であり、何らかの (かなり小さい) 定数係数を与えるか取る必要があります。ここでは明らかにそうではありません。科学表記法で結果の指数を見ると簡単にわかるように、これは反復ごとに桁数が約 2 倍になります。

私は絶対に確信しているわけではありませんが、内側のループを O(log N) ではなく O(log log N) のようなものにすると思います。外側のループがおそらく O(N) であることを意図していることに同意するのはかなり簡単だと思います (ただし、現在は 1 回だけ実行するように記述されています) O(N log log N)。

実用的な観点から、多くの場合、本質的に定数として扱うことができることを追加する義務があると感じてO(log log N)います。上記のように、典型的な倍精度浮動小数点数で指定できる上限は、わずか 11 回の繰り返しで到達します。そのため、ほとんどの実用的な目的では、全体的な複雑さは として扱うことができますO(N)。

[おっと -- 私がこれを書いているときに彼が答えたことに気付かなかったが、@jwpat7 は私とほぼ同じ結論に達したようだ. 彼/彼女に称賛を。]

于 2012-10-30T17:25:30.923 に答える
2

i2 番目のループは、 に達するまでの値を 2 乗しますk。定数項を無視すると、このループはO(log k)時間内に実行されます。

なんで？なぜなら、解けi^m = kば が得られるからm = constant * log(k)です。

あなたが言ったように、外側のループはO(n)時間内に実行されます。

の値が大きくなると、内部ループが で実行され、全体の複雑さが になりkます。nO(log n)O(n log n)

于 2012-10-30T16:34:51.210 に答える