0

有人可以帮我找到这个循环的严格运行时界限：

for(c4=0, i=1; i<=n; i = 2*i)
   for(j=1; j<= i; j++)
       c4++;

我不确定如何处理外循环中的 2*i，我认为内循环类似于 O(i-1)/1 并且就 n 而言是 O(n-1) 因为而我<=n。

提前致谢。

4

1 回答 1

1

外循环将运行log(N)时间。对于每个外循环，内循环将运行i时间。并且i从 1, , 2, 4, 8, 16, ..., log(N) 开始。

所以总数约为 2^(log(N)) - 1，它是 O(N)

于 2013-09-27T02:49:53.490 回答