performance - 在分析这个插入排序算法时，求和是什么意思？

Question

对于这种插入排序的分析，如算法介绍中所示：

在此处输入图像描述

第 5 行的总和说明了什么？我很困惑tj应该是什么意思。为什么它不只是表明它发生了 n*n 次之类的？

有人可以澄清它在说什么吗？

score 3 · Accepted Answer

tj 是 while 循环执行的次数（对于给定的 j 值）

这是一个取决于数组初始顺序的变量

score 1 · Accepted Answer

while loop(iterates i)嵌套在for loop(iterates j). j因此，对于外循环中的每个值，inner loop(i)迭代t_j次数。

t_j = (number of times while loop iterates for each j). 因此，总体总成本将是所有j迭代的成本总和，即sigma{for all j=2..N}(t_j)

2 回答 2