algorithm - 插入排序算法的CORMEN解释

Question

在 CLRS 的算法导论 一书的插入排序的解释中，我无法理解 sigma(求和)符号的这种特殊用法:

令 tj 表示第 5 行中的 while 循环测试针对该 j 值执行的次数。

有人可以解释第 5、6、7 行中 sigma(求和)的用法吗？我知道求和公式和用途。

Answer 1

我想我终于可以清楚地理解了。

Sigma 表示对于每个 j，while 循环最多可以运行 t 次。因此，当 j 等于 2 时，while 循环将运行 t 次，当 j 等于 3 时，while 循环将运行 t 次，但是由于我们不知道这个 t 是否等于 j=3 时对于前面的t，当j = 2时，我们加一个下标表示有不同的t。

求和从2到n，这已经代表了在外层运行的for循环。

所以，总而言之，限制是从 2 到 n，每次我们进入 for 循环并进入 while 循环时，这个 while 循环将运行 t 次。