java - 嵌套 for 循环时间复杂度

Question

对于给定的代码，Big - O 表示法的时间复杂度是多少？

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

第一个循环需要 logn 时间，但是第二个循环呢？我很困惑，请帮助我理解这一点。

Answer 1

外层循环的复杂度为O(log n)，因为它运行的次数与log(某个数字n)成正比。

内部循环(仅由其自身执行)的时间复杂度为O(n)，因为它运行的次数与某个数字 n 成正比。对于外循环的每次迭代都是如此，因为时间复杂度保持不变，即它始终与调用时的 n 值成正比。

整段代码的复杂度为O(n log(n))。通常表示“大约是某个数字 n 乘以 log(n)”。

大 O 表示法旨在分类，而不是量化。它给出了所讨论的函数如何在不同大小的数据集上执行的一些想法。被描述为具有 O(n log(n)) 性能的两个函数对于给定的 n 值可能会有很大差异。