如何計算此功能的時間複雜度？

大家好我試圖計算這個函數的時間複雜度，但我不能真正理解如何計算是個「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：我如何寫數學符號，我不能在編輯器中

來源

2016-06-21 Giorgio M.

在兩地:) –

外循環執行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）），但是他們犯的錯誤是將外部行程計數乘以內部環路的最大行程計數。爲了得到正確的答案，你需要考慮到內部循環計數每次增加一倍，所以後面的計數比先前計數矮。

來源

2016-06-21 14:48:09

它實際上是非常棘手的問題找到任何東西。技術上你的觀察是正確的。內循環將執行到n次，所以看起來複雜度爲O(n*log2(n))。

但這不是真的正確。問題是，對於while的第一次執行，內部for循環會執行一次，下一次執行兩次，下一次執行四次等等，直到n/2（四捨五入爲下一次冪，因此最大爲n）。總共它總計爲1+2+...n/2，這是O(n）。即線性複雜度。

來源

2016-06-21 14:43:36

對於第一次迭代，內部循環將運行一次，對於第二次運行，對於第三次迭代，內部循環將運行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）

來源

2016-06-21 14:55:49

如何計算此功能的時間複雜度？

回答

相關問題