この関数の時間複雑度はどのように計算されますか？

Question

こんにちは皆、私は、この関数の時間計算量を計算しようとしましたが、私は本当に「forループ」というの複雑さを計算する方法を理解することはできません

01 int* f(int a[], int n) { 
02 int i = 1; 
03 int *s; 
04 s = calloc(n, sizeof(int)); 
05 while (i < n) { 
06  for (j=0; j < i; j++) 
07   s[i] = s[i] + a[j]; 
08  i = i*2; 
09 } 
10 return s; 
11 } 

運動はに関連して、時間の複雑を要求配列

の寸法「N」私は私がわき "を残せば、彼らはwhileループの場合（1）複雑

Oを持つ必要がありますので、ライン02,03,04は大きな問題であるとは思いません時間複雑度が2^k<n --> k= log_2(n)であるはずであるたびに、「i」に2を掛けているため

forループはどうですか？ 「i」回実行する必要がありますが、「n」に関してこれをどのように表現できますか？

P.S：？どのように私は数学記号を書くのですか私はそれが実際には難しい質問ですねエディタ

Answer 1

外側ループはiは値1、2、4、8、... < nが2の最大パワーnよりも小さい< Nを取ると、log(n)回実行されます。

iの各値に対して、内側ループはi回実行されます。

あなたは1 + 2 + 4 + 8 ... + <です。この合計は2 * n未満です。だから答えはO（n）です。

これはO（n * log（n））だと思った人もいましたが、間違いは外側のトリップ数に内側のループの最大トリップ数を掛けたものです。正解を得るには、内側のループトリップ数が毎回2倍になることを考慮する必要があります。そのため、後のトリップ数は前のトリップ数を小さくします。

Answer 2

で何かを見つけることができません。技術的にあなたの観察は正しいです。内部ループはn回まで実行されるため、複雑さはO(n*log2(n))のように見えます。

しかし、それは本当に正しいわけではありません。問題は、whileの最初の実行のために、内部forループが1回、次回の2回、次回の4回など、最大でn/2（2の次の累乗に丸められ、したがって最大でn）まで実行されるということです。だからそれは合計で1+2+...n/2であり、これはO(nです）。私。線形の複雑さ。

Answer 3

最初の反復の内部ループは1回、2回目は2回、3回目の反復は内部ループが4回実行されます。だから、

2^0 + 2^1 + 2^2 + 2^3 +.....+2^i where 2^i < n 

我々はそうnの前の値がn/2

だろう i=log2(n)

2^0 + 2^1 +...+2^(log2(n)) ie 2^0 + 2^1 + ...+ n 

しかし

i < log2(n) and not i=log2(n). 

を与える2^i < nのlog両側を取ることによってiを見つけることができます210

だから最終的に我々が持っている

2^0 + 2^1...+n/2 

支配的な用語がn/2あるので、そのO（N/2）Oである（n）の両方に