while 循环的总体 Big-O 复杂度，内部步骤随着每个循环而增加

Overall Big-O complexity of a while loop, with inner step that increases with every loop

刚开始学习复杂度分析，搞不懂这部分算法整体的Big-O复杂度，这个应该怎么计算？

Code Fragment               Time Complexity
1 -  C = 0                  O(1)
2 -  while C <= L           O(L)
3 -      f(C += 1)          O(???)

步骤3其实需要更多的步骤，但可以概括为一个函数f执行了C步

我的问题是每次迭代都会增加 C，因此我们将不胜感激任何帮助或指导。

如果 f(C) 采取 C 步并且 C 在每次迭代中增加到值 L 那么算法是 O(L^2).

让我们在其中插入一些数字，看看会发生什么。

  • 对于L=0，第3步运行一次0步；
  • 对于L=1，第3步运行两次0，然后1步；
  • 对于L=2，第3步运行3次0、1、2步；
  • 对于L=3，第3步运行4次，分别为0、1、2、3步；
    [...]
  • 对于 L=C，步骤 3 使用 0、1、... 和 C=L 步骤运行 n 次。

假设"zero steps"是常数时间，把它改成1。所以有两种方法可以回答这个问题：

  • 您的函数运行 1+1+2+3+..+L 步。那是 1 + 一系列 L 元素，总和为 1 + L * (L + 1) / 2，所以它是 O(L2);
  • 它运行 L 次可以限制为 O(L) 的函数，所以它是 O(L2).

如果 function f() DOESN'T change C ... 那么你展示的三行的整体复杂度是 O(N)：时间将线性增加L - C 的大小增加了。第 1 行和第 3 行都没有贡献：它们本质上都是 "constant".

如果函数 f() 确实 改变了 C（例如使用全局变量），那么第 2 行和第 3 行都有贡献，cjungel 和 giusti 的答案是正确的O(L^2).

这是一篇很棒的文章：

https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html