大家好我試圖計算這個函數的時間複雜度，但我不能真正理解如何計算是個「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」
我不認爲線02,03,04是一個大問題，因爲他們應該有一個O（1）複雜
while循環，如果我撇開「 for循環「一會兒，因爲每次時間複雜度應爲2^k<n --> k= log_2(n)時，」i「乘以2
但是for循環呢？它應該被執行「我」倍，但我怎麼能表達這個關於「n」？
P.S：我如何寫數學符號，我不能在編輯器中
外循環執行log(n)次，其中i取值1,2，4，8，...，< n，其中< n是最大功率2小於n。
對於i的每個值，內循環執行i次。
所以你有1 + 2 + 4 + 8 ... + < n。這個總和小於2 * n。所以答案是O（n）。
其他人認爲這是O（n * log（n）），但是他們犯的錯誤是將外部行程計數乘以內部環路的最大行程計數。爲了得到正確的答案，你需要考慮到內部循環計數每次增加一倍，所以後面的計數比先前計數矮。
它實際上是非常棘手的問題找到任何東西。技術上你的觀察是正確的。內循環將執行到n次，所以看起來複雜度爲O(n*log2(n))。
但這不是真的正確。問題是，對於while的第一次執行，內部for循環會執行一次，下一次執行兩次，下一次執行四次等等，直到n/2（四捨五入爲下一次冪，因此最大爲n）。總共它總計爲1+2+...n/2，這是O(n）。即線性複雜度。
對於第一次迭代，內部循環將運行一次，對於第二次運行，對於第三次迭代，內部循環將運行4次，等等。所以
2^0 + 2^1 + 2^2 + 2^3 +.....+2^i where 2^i < n
我們可以通過利用2^i < nlog雙方找到i這給i=log2(n)
2^0 + 2^1 +...+2^(log2(n)) ie 2^0 + 2^1 + ...+ n
但
i < log2(n) and not i=log2(n).
所以n以前的價值將是n/2
所以最後我們
2^0 + 2^1...+n/2
的主項是n/2所以它爲O（n/2），這是O（n）
在兩地:) –