3

次の関数の複雑さを計算しようとしています:

k=n;
while(k>0)
  g(n);
  k=k/2; {Comment: this is integer division, so 1/2=0}
end while;
for(j=0;j<m;j++)
  f(m);

具体的には、while ループの複雑さです。g(n) の複雑さは O(n) だと言われましたが、その複雑さがどの程度になるのか、どのように解決するのかわかりません。複雑さがO（0.5n ^ 2）ではないことに気づきましたが、毎回半分になるため、計算方法がわかりません。誰にもアイデアはありますか？

4

3 に答える 3

4

g(n) が O(n) の場合、複雑さは O(n*log(n)) です。

さらに説明するために、g(n) を無視してみましょう。

k = n;
while(k > 0) {
    k = k / 2;
}

n = 1000としましょう

次に、次の k の値を取得します。

Pass | k
-------------
 0   | 1000
 1   | 500
 2   | 250
 3   | 125
 4   | 62
 5   | 31
 6   | 15
 7   | 7
 8   | 3
 9   | 1
 10  | 0 (stopped)

log(1000) = 9.96 k をゼロにするのに 10 回の反復しかかからなかったことに注意してください。これは、log(n) 計算の複雑さの例です。

次に、ループ内に g(n) を追加すると、反復ごとに O(n) を追加することになり、O(n*log(n)) の総計が得られます。

于 2013-01-16T22:26:32.467 に答える
2

while ループの複雑さは明らかO(n log n)です。log n各反復の終わりにk2 で除算されるため、反復があります。反復の数を取得するにnは、2 のべき乗として表します (2^x とします)。もし2^x=n, then x = log n。そのため、while ループの複雑さは ですO(n log n)。nは 2 の累乗ではないため、混乱しないでください。つまりlog n、常に整数であるとは限らず、log n, の代わりに と書く必要があります。[log n]ここで、[y]は の整数部分ですy。[log n]常に aとして表すことができますc* log n。c は定数であり、アルゴリズムの複雑さは変わりません。[]したがって、関数は必要なく、O(n log n)受け入れられ、正しい答えです。

for ループの複雑さは、 の複雑さに依存しますf(m)。O(f(m)) がO(1)の場合、ループは O(m) ですO(f(m))がO(m)、 の場合、ループはO(m^2)です。もアルゴリズムの一部であるため、コード全体の複雑さを確認したい場合f(m)は、) の複雑さを知る必要があります。f(

于 2013-01-17T20:43:42.277 に答える
0

アルゴリズムの複雑さは次のとおりです。

最初のループは O(logn) 回実行され、各反復は g(n) を実行する必要があります。したがって、

O(sum{i from 0 to log(n)}{O(g(i))}).

2 番目のループは m 回実行されます。それはとります：

O(sum{j from 0 to m}{O(f(i))})

アルゴリズムの全体的な複雑さは次のとおりです。

O(sum{i from 0 to log(n)}{O(g(i))}) + O(sum{j from 0 to m}{O(f(i))})
于 2016-06-22T10:59:02.887 に答える