如何计算此功能的时间复杂度？

大家好我试图计算这个函数的时间复杂度，但我不能真正理解如何计算是个“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

如何计算此功能的时间复杂度？

回答

相关问题