0

私が解決しようとしている問題があり、助けていただければ幸いです。の時間複雑度はどのくらいですか...

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

外側の for ループは n 回実行されます。k+= log n内部ループでの処理方法がわかりません。私の考えでは、それは O(n^2) です。k に log(n) を追加しても n ループが追加されるわけではありませんが、O(n*log n) よりも少ないと思います。明らかに、それは単なる推測であり、それを数学的に示す方法を理解するための助けがあれば大歓迎です!

4

3 に答える 3

0

log(n)ここでは定数として扱うことができます。

ループの各反復は、一定量の作業 ( ) を/sum+=...; k+=...に等しい回数実行します。ループの繰り返しがあります。したがって、総作業はです。nlog(n)nn^2 / log(n)

次のような一連の操作が表示されるときはいつでも:

 ---------------------b-------------------------
 |O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
 |O(blah) + O(blah) + O(blah) + O(blah)     .
a|O(blah) + O(blah) + O(blah)               .
 |O(blah) + O(blah)                         .
 |O(blah)     .         .         .         .

それはa*b * O(blah)-- 正方形を想像してみてください (ここに.s を置きます)。これは、2D 長方形 (長方形の半分) の一定の割合であるため、O(a*b).

上記の場合、 b= n、 a= n/log(n)、および O(blah)= O(1)(内側のループから)

于 2011-05-02T20:55:54.673 に答える
0

あなたは非常に簡単に「ただまとめる」ことができます：

あなたが言ったように、外側のループにはnステップがあります。内側のループには(k-j) / log nステップがあります。

それは（おおまかに）：

 n
---
\     (n-j)             n*n
/   -------- = ... = ---------
___  (log n)          2*log(n)
j=1

というわけで、O((n^2)/log(n))合計です。

于 2011-05-02T20:57:19.450 に答える