分析包含while循环的算法

Question

在分析算法时，我通常不会遇到for loop的问题，而我在分析涉及while loop的算法的运行时间时确实会遇到问题。我将展示一个例子来表达我的问题。

下面是我正在研究的coin-change algorithm (我们大多数人都知道的算法)的一部分：

counter = 0
s = 0
while(s <= n/100)
   s = s+1
   t1 = n- 100*s
   h = 0
     while(h <= t1/50)
          h = h +1
          t2 = t1 - 50*h

...

有人能解释一下知道嵌套while循环的算法运行时间的最好方法吗？

Answer 1

while循环只是编写for循环的另一种方式，因此评估复杂性应该没有什么不同。

在这里，外部while循环在复杂世界中运行n次(在现实世界中与n成正比)，因为s在每次迭代中增加1，并且它一直运行，直到s达到与n成比例的值。

内部循环，我想你可能有点困惑，它运行t1次(同样是在复杂世界中)，其中t1 = n - 100s。现在你认为算法是O(n^2)，但t1在每次迭代中都会减少，因此内部循环在每次后续迭代中运行的次数更少，并且可能不是O(n^2)。

每次迭代的次数是不同的，因此整个迭代集将运行：n - 100 + n - 200 + n - 300 + .... 0 t1。由于此系列中的项数与n成正比，因此求和将具有n平方项，并且为了报告复杂性，将忽略所有低阶项，因此您无需担心其余数字的总和。该算法是O(n^2)。

诀窍是在每一步忽略常量和低阶项，这就变得很容易了！