algorithm - 计算内循环的时间复杂度

Question

所以我正在学习如何计算算法的时间复杂度，来自 Cormen 的 Introduction to Algorithms。书中给出的例子是插入排序:

1. for i from 2 to length[A]
2.    value := A[i] 
3.    j := i-1
4.    while j > 0 and A[j] > value
5.       A[j+1] := A[j]
6.       j := j-1
7.    A[j+1] = value  

行 1. 执行了 n 次。
4. 行，按照书上的说法，执行次。

那么，作为一般规则，是否所有内部循环的执行时间都用总和来表示？

Answer 1

有趣的是，大多数循环都可以用求和来表示。一般来说这不是真的，例如我可以创建循环

for(int i = n; i > 1; i = ((i mod 2 == 0) ? i / 2 : 3 * i + 1)))

即初始化 i至 n , 在每次迭代中如果 i甚至将它除以二，否则乘以 i三加一，当 i <= 1 时停止.这有什么大不了的？ Nobody knows .

显然，我从未见过使用如此奇怪循环的真实程序，但我见过 while 循环根据可能在迭代之间发生变化的某些任意条件来增加或减少计数器。