algorithm - 选择排序 CLRS - 推理的正确性

Question

我是一名自学计算机科学专业的学生。现在我正在阅读 CLRS，我做了 2.2-2 练习，它是关于选择排序的。

First array subscript is 1.

我写的伪代码是:

FOR i=1 to A.length - 1
    FOR j=i+1 to A.length
        IF A[j] < A[i]
            new_index=j
    IF new_index > i
        tmp = A[i]
        A[i] = A[new_index]
        A[new_index] = A[i]

我的推理是:
第一个循环测试执行 n 次(1、2、3 ... n)。当 i 变为 n 时，循环停止。所以第 5 行被执行 (n-1) 次，依此类推。

然后我认为第二次循环测试执行了(n^2 + n - 2)/2次。当初始 j = 2 时，假设:2, 3, 4, 5 ... (n + 1)，循环测试执行 n 次，当 j = 3 时，循环测试执行 (n - 1) 次，依此类推在。所以当 j = n 时，循环测试执行了 2 次。

为此执行第二个循环测试:2 + 3 + 4 + 5 + ... + n = [(n-1)*(n+2)]/2 = (n^2 + n - 2)/2。所以第二个循环的内部 if 被执行:1 + 2 + 3 + 4 + ... + (n-1) = [(n-1)*n]/2。

在写这篇文章之前，我阅读了很多假设性的解决方案，但没有人能与我的相提并论。所以我想知道我的推理是否错误。

我希望我以良好的形式写下所有细节。

Answer 1

伪代码是正确的，你的分析是正确的，但你的解决方案在推理上有一些错误。

---

一些技巧

Then I think that the second loop test is executed (n^2 + n - 2)/2 times

它执行了 n(n-1)/2 次。请参阅下面的解决方案。

When initial j = 2, it assumes: 2, 3, 4, 5 ... (n + 1), the loop test is executed n times,

记住密码是:FOR j=i+1 to A.length ，因此当内部 for 循环从 j = 2 开始时，它上升到 j = A.length，即它上升到 j = n。换句话说，它重复执行了 j = 2, 3, 4, ..., n 次，所以总共执行了 n - 1 次，而不是 n 次!

For this reason the second loop test is executed: 2 + 3 + 4 + 5 + ... + n = [(n-1)*(n+2)] / 2 = (n^2 + n - 2) / 2. So the inner if of the second loop is executed: 1 + 2 + 3 + 4 + ... + (n-1) = [(n-1)*n] / 2.

假设第二个循环的 if 语句体 always 执行(if 条件为 always true)，那么它应该执行与第二次循环测试。所以我在这里不遵循你的推理。至于求和，要找到迭代次数，您需要添加以下内容:

• j = 1: 执行 (n-1) 次
• j = 2: 执行 (n-2) 次
• j = 3: 执行 (n-3) 次
• ...
• j = n: 执行1次

所以你需要加起来:(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2

---

解决方案

1. 内部的 for 循环执行了 恰好 C(n, 2) = n(n-1)/2 次。循环生成所有对 (i,j)，使得 1 <= i < j <= n – 从组合学来看是 n-choose-2，或 C(n, 2)。
2. if 语句主体 ( new_index=j ) 执行最多 n(n-1)/2 次——我们不知道确切的次数，因为我们不知道其中的值是什么A是——所以我们不知道有多少次A[j] < A[i] .它可以执行零次(考虑对数组进行排序的情况)。但是，尽管如此，我们还是通过假设条件始终为真来找到上限。在这种最坏的情况下，if 语句的主体执行的次数与内部 for 循环的执行次数相同——从前面的要点来看是 n(n-1)/2
3. 通过类似的推理，另一个 if 语句体(执行交换的那个)执行至多 n 次。

因此，总的来说，该算法恰好执行 n(n-1)/2 次具有 ϴ(1) 工作的内部 for 循环迭代的迭代 - 以及恰好 n 次迭代的 if 语句在 ϴ(1) 时间内执行交换。这给出了 ϴ(n^2) 的时间复杂度。