时间复杂度（嵌套循环）

你如何计算出这个的时间复杂度？时间复杂度（嵌套循环）

int count=0; 

for (int i=1 ; i < n; i*=4) 

    for (int j=1;j<=n;j++) 

       count++;

2016-08-22 WWBM

至少需要格式化你的几行代码的时间。此外，你寻求帮助，但并没有真正解释你卡在哪里。你基本上只是给了我们一项家庭作业。 –

试图找出如何从代码片段获取T（n）。将t（n）= O（n^2）还是O（log（n））。它不是作业。这是来自过去测试的一个问题。只是真的有一个理解它的问题 – WWBM

你为什么认为这将是其中之一？同样，你应该解释你理解它的方式，并且非常具体地说明你困惑的部分。 –

TL;博士：在发布代码的复杂性：O(nlogn)

让我们来分析它从内到外。对于i的每个值，内循环重复自己精确地为n次。

外循环重复自身，而i < n和i每次乘以4。这意味着，在第一次迭代之后，i=1，然后i=4, i=16, i=64, ....和k'th迭代i = 4^(k-1)之后。
这意味着，在停止时：

i >= n 
4^(k-1) >= n 
log_4(4^(k-1)) >= log_4(n) 
k-1 >= log_4(n).

这意味着外环将重复log_4(n) + 1。

总结它一起带给你内在的循环重复n*(log_4(n)+1)倍，这是O(nlogn)

2016-08-22 20:09:38 amit

非常感谢你！老实说，让更多的感觉！ – WWBM

回答