在 CLRS 的算法导论 一书的插入排序的解释中,我无法理解 sigma(求和)符号的这种特殊用法:
令 tj 表示第 5 行中的 while 循环测试针对该 j 值执行的次数。
有人可以解释第 5、6、7 行中 sigma(求和)的用法吗? 我知道求和公式和用途。
最佳答案
我想我终于可以清楚地理解了。
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 次。
关于algorithm - 插入排序算法的CORMEN解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48328001/