你如何找到影响彼此的循环运行时间？

Question

我不知道这些种类的循环的技术术语（如果存在的话），所以我会提供了一个例子：

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

在这个例子中，while循环，直接改变的次数数for循环运行，这是由于某种原因，我抛弃

通常，我会一行一行地看看每行会运行多少次，但由于次数的变化，我试着做一个总结，但得到了一个一点点迷路...什么是解决这类问题的一步一步办法？

在笔记答案是O（n），但我这样做时，我得到n日志

任何帮助表示赞赏（N），这是审查我的最后

另外，如果你知道任何好的地方找到这种类型的练习题，我将不胜感激！

谢谢

Answer 1

我想分析这个代码是非常相似的人在这个lecture找到了一条建设最大堆的程序的运行时间。对它的直接分析导致了nlgn的复杂性，但当使用求和进行分析时，结果就像你的问题一样。

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

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