2

我目前正在阅读 TCRC Introduction to Algorithms 3rd edition 教科书的第 2 章，并且正在阅读作者对该算法的循环不变量的解释。我理解作者的初始化和维护逻辑。然而，终止是我有点陷入困境的。作者声称在终止时，j = n + 1。然而，在算法的伪代码中，j 从 2 循环到 n。所以不应该 j = n - 1 吗？

编辑：这本书的插入排序伪代码是：

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into sorted sequence A[1...j - 1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i  - 1
    A[i + 1] = key

编辑：仔细阅读后，我终于明白了为什么 j = n + 1 在终止期间。这是因为 for 循环从 2 变为 n（包括），所以在 j 超过 n 之后，循环终止，因此在终止时 j = n + 1。我很感激帮助。

4

1 回答 1

1

免责声明：这可能是完全不正确的......这只是一个脑吐。

旁注：由于j在此循环期间递增，因此起点与结束条件无关。

 for j = 2 to A.length //A.length = n in your question

这个伪代码有一点歧义。

首先，我们假设j是在这个for循环之外定义的，并且在循环终止时会有一个结束值。 见@Dukeling 的评论

j其次，您的代码使用as 索引器以数组为目标：A[j]

toin这个词存在歧义for j = 2 to A.length，是包含还是排除A.length？并且有这个索引器A[j]

在常见情况下，对于 中的索引器A[j]，有效范围j为[0...A.length -1]

有些语言使用另一个范围，即：[1...A.length]我认为这是作者的意图，因为A[0]根本没有被击中。

如果是这种情况......并且for条件在它打破循环之前递增j（以测试条件并查看它是否为假），那么......你会得到j = A.length + 1.

作为旁注：

与语言C一样，数组的有效范围为[0...A.length -1].

在这个 C 示例中，c具有A.lengthafter 终止的值：

int c = 0;
for (c = 3; c < A.length; c++)
{

}
//c = A.length after the loop is completed.
于 2017-11-07T23:11:39.357 回答