算法时间复杂度：i/= 2在循环中

int fun(int n) { 
    int count = 0; 
    for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
      count += 1; 
    return count; 
}

我是一个非常新的时间复杂性计算。对于这个算法，我得到的答案是O（nlogn），但答案显然是O（n）。算法时间复杂度：i/= 2在循环中

我的逻辑是外环有一个指数下降，并会发生log_base2_（N）次。内循环将总共运行N次，因为它变成了几何和（第一次迭代是N/2次，然后是N/4，然后是N/8 ...）。如果我把它们放在一起并且由于嵌套循环而使它们相乘，那就是我用O（NlogN）提出来的地方。我错过了一些明显的东西吗？

来源

2017-09-13 user6142489

外循环将运行总共log（n）次。现在，如果你看到它第一次运行n次，接下来的N/2次等等，所以使得该系列

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

这个总和将（2 * N）内循环，这意味着它是O（n）

因此时间复杂度是O（n），因为外部循环运行O（logn）次并且内部循环运行O（n）次。

这不是O（nlogn）由于内环路不采取n步时，都实际上采取的所有步骤的总和将是O（n）的

来源

2017-09-13 11:03:03 marvel308

这是有帮助的。我认为我把操作的总数与运行时间混淆了。如果我正确理解你的观点，时间复杂性将是两个循环中的更糟糕的情况，在这种情况下是O（n）。 – user6142489

@ user6142489通常，它不是两个循环中最差的，而是最内层循环的总迭代次数。因此，正如在这个答案中指出的那样，我们需要执行给出O（n）的总和的相应总和。然而请注意，通常的过程是采用每个循环的复杂性（因此不是_max_）的_product_，但是这会导致一个太松的界限，因为最内层循环的迭代次数取决于当前的_一世_。 – qwertyman

有趣。谢谢。 – user6142489

算法时间复杂度：i/= 2在循环中

回答

相关问题