10

私はここに短いプログラムを持っています：

Given any n:
i = 0;
while (i < n) {
   k = 2;
   while (k < n) {
        sum += a[j] * b[k]
        k = k * k;
   }
   i++;
}

この漸近的な実行時間はO（n log log n）です。なぜそうなのですか？プログラム全体が少なくともn回実行されることがわかりました。しかし、loglognを見つける方法がわかりません。内側のループはk*kに依存しているため、明らかにn未満になります。そして、毎回k / 2の場合、nlognになります。しかし、どのようにして答えがlog log nであるかを理解しますか？

4

3 に答える 3

8

数学的証明のために、内部ループは次のように書くことができます。

T(n) = T(sqrt(n)) + 1

w.l.o.g assume 2 ^ 2 ^ (t-1)<= n <= 2 ^ (2 ^ t)=>
we know  2^2^t = 2^2^(t-1) * 2^2^(t-1)
T(2^2^t) = T(2^2^(t-1)) + 1=T(2^2^(t-2)) + 2 =....= T(2^2^0) + t =>
T(2^2^(t-1)) <= T(n) <= T(2^2^t) = T(2^2^0) + log log 2^2^t = O(1) + loglogn

==> O(1) + (loglogn) - 1 <= T(n) <= O(1) + loglog(n) => T(n) = Teta(loglogn).

合計時間はO（n loglogn）です。

なぜ内部ループはT（n）= T（sqrt（n））+1ですか？ 最初に、内部ループがいつ中断するかを確認します。k> nの場合、kが少なくともsqrt（n）になる前、または最大でsqrt（n）になる前の2レベルであるため、実行時間はT（sqrt（n））になります。 +2≥T（n）≥T（sqrt（n））+1。

于 2011-03-05T10:17:29.360 に答える
0

ループ変数が一定量だけ指数関数的に減少/増加する場合、ループの時間計算量はO（log log n）です。ループ変数を一定量で除算/乗算すると、複雑さはO（Logn）になります。

例：あなたの場合、kの値は次のとおりです。括弧内のiは、ループが実行された回数を示します。

 2 (0) , 2^2 (1), 2^4 (2), 2^8 (3), 2^16(4), 2^32 (5) , 2^ 64 (6) ...... till n (k) is reached. 
The value of k here will be O(log log n) which is the number of times the loop has executed.

n仮定のために、それがであると仮定しましょう2^64。現在log (2^64) = 64、log 64 = log (2^6) = 6.したがって、プログラムはである6ときにn実行されました2^64。

于 2017-06-17T09:57:23.460 に答える
0

コードがこのような場合、n *lognである必要があると思います。

i = 0;
while (i < n) {
    k = 2;
    while (k < n) {
        sum += a[j] * b[k]
        k *= c;// c is a constant bigger than 1 and less than k;
    }
i++;
}
于 2019-09-19T13:20:23.787 に答える