插入排序算法分析

Question

我对 CLRS 的“算法简介”第二版（第 25 页）一书中插入排序算法的成本和时间感到困惑。

这是具有成本和时间的算法：

Insertion-Sort(A)                        cost   times
1. for j <- 2 to length[A]                c1    n
2.     do key <- A[j]                     c2    n-1
3.       //Insert A[j] into the           0     n-1
         //sorted sequence A[1..j-1]
4.     i <- j - 1                         c4    n-1
5.     while i > 0 and A[i] > key         c5    sum_{j=2}^n t_j
6.         do A[i+1] <- A[i]              c6    sum_{j=2}^n (t_j-1)
7.         i <- i - 1                     c7    sum_{j=2}^n (t_j-1)
8.     A[i+1] <- key                      c8    n-1

我不明白，为什么

值

"times" is equal to n

对于上面第 1 行中的外部 for 循环。

假设我们有一个数组“A”，如下所示：

A = [5, 2, 4, 6, 1, 3]

那么数组的长度就是6。

那么，

for j <- 2 to length[A]

这意味着，我们从索引 2 迭代到索引 6，即 5 次。

在这种情况下，我想，对于上面的外部 for 循环，如果 n 是数组中元素的总数，我们将迭代 (n-1) 次。

所以，我不确定为什么第 1 行（即 out for 循环）的“times”值是 n 而不是 (n-1)。

谢谢。

安迪

Answer 1

我认为他们的想法大致如下。一个循环

for j <- 2 to n
    do stuff

等价于：

j <- 2
while j <= n
    do stuff
    j <- j+1

它将测试

j

等于 2, 3, ...,

n

, 和

n+1

的条件。因此，即使循环体只执行

n

次，它也需要进行

n

比较。

考虑一个极端情况可能会有所帮助：假设 n=2。然后我们将：设置 j=2，检查 j <= n (yes), do stuff, set j=3, check j <= n (no), done. Two comparisons of

j

与

n

，而不仅仅是一个。

Answer 2

感谢您的所有回答。在我看来，令人失望的是，作者没有明确讨论他们如何确定该伪代码中每一行的成本函数的意图。给一个或多个学生或专业人士（比如我自己）留下深刻的印象是非常糟糕的，因为他们在 20 年的差距后才开始学习算法分析！

再次感谢大家。每次我需要帮助时，你们都太棒了。

Answer 3

让我们考虑一个数组

int array={1,2,3,4,5,6,7,8,9}

循环从 2 开始，到 9 结束

for j <- 2 to length[A]

此条件检查 2,3,4,5,6,7,8,9 条件检查次数等于8， 但它也会检查 10 并终止循环 所以条件检查的次数等于 9。 这等于数组中的元素数量。

n=9