1

誰かが次のループの時間の複雑さを見つける方法を理解するのを手伝ってくれませんか:

    for (int j = 1 to n) {
      k = j;
       while (k < n) {
        sum += a[k] * b[k];
        k += log n;
       }
     }

ここで、n 2 / log(n)である解決策を見つけました。

外側のループが n 回かかることは明らかですが、内側のループについては行き詰まっています。n / log n 係数はどこから来たのですか?

用語ごとにフォローしようとしましたが、続けることができませんでした

1st time k = 1,
2nd time k = 1 + log n
3rd time k = 1 + log n + log n  //   (2 log n)

stuck here :(

パターンを見つけるにはどうすればよいですか、またはそのようなコードの時間の複雑さを得るために従うべき最善の手順は何ですか?

4

2 に答える 2

1

明らかに、外側のループは n 番目の順序で実行されます。問題は、内側のループにかかる時間はどれくらいかということです。ループは で終了しk >= n、 でk始まりj、 のステップで増加しますlog(n)。約かかります

n / log(n)

から までの反復回数(丸め誤差を与えるか取るか)のステップで合計1します。しかし、常に からまで行くとは限りません- 時々から、または、または...nlog(n)1n10n20n/2

(n - i) / log(n)

(または...)iの代わりに開始すると、内側のループが明示的に実行された合計回数を合計として書くことができます。10

total number = sum(i = 1 to n, (n - i) / log(n))
             = sum(i = 1 to n, n / log(n)) - sum( i = 1 to n, i / log(n))

             = O(n * n / log(n)) - something smaller than that.

「小さい項」は、最初の項の約半分です。

sum( i = 1 to n, i ) = n * (n + 1) / 2;

しかし、計算の順序を見ると、そのような定数は問題ではありません。大きくなるときに何が起こるかを知りたいだけなnので、アルゴリズムは で実行されると言いたいかもしれませんが、単にそれが実行されますO( (1 - 0.5) * n2/log(n))O( n2/log(n))

今見えますか？

于 2013-09-06T20:18:24.173 に答える