你如何找到相互影响的循环的运行时间？

Question

我不确定这些循环的技术术语（如果存在的话），所以我将提供一个示例：

x=0
i = 1
while(i<n)
    for(j=1 to n/i)
        x = x + (i-j)
    i*=2
return(x)

在这个例子中，while 循环直接改变了 for 循环的次数 运行s，这让我不知何故感到困惑

一般情况下，我会逐行查看每行会出现多少次运行，但由于次数变化，我尝试求和但有点迷路...什么会是解决这类问题的循序渐进的方法吗？

笔记中的答案是O(n)，但是当我这样做时我得到了nlog(n)

感谢任何帮助，这是我期末考试的复习

此外，如果您知道可以找到此类练习题的任何好地方，我将不胜感激！

谢谢

Answer 1

我认为对这段代码的分析与lecture中找到构建最大堆过程的运行时间的代码非常相似。对它的直接分析导致了 nlgn 的复杂性，但是当使用求和分析时，结果证明它是 n 就像你的问题一样。

所以回到你的问题，外循环运行 次和内部运行 n / i。但由于 i 呈指数增长，我们可以使用另一个变量 j，它在循环迭代中增加一次，因此它可以用于求和并根据关系 .

更改边界

总和是 求和是一个几何数列，其结果是 所以当n趋于无穷大时，它收敛于一个常数（2）。因此，总和被认为是一个常数因子，不会影响代码的渐近复杂度，它仅为 O(n)。