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

Question

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

第一个数组下标为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)。当我变成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

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

一些小贴士

然后我认为第二个循环测试是执行(n^2 +n- 2)/2次数的。

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

当初始j=2时，它假设: 2，3，4，5.(n + 1)，循环测试执行n次，

记住代码是：FOR j=i+1 to A.length，所以当内部for循环在j=2时开始时，它会上升到j= A.length，即上升到j= n。换句话说，它对j= 2，3，4，…，n重复执行，所以总共执行n-1次，而不是n次！

为此，执行了第二循环测试: 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。

假设第二个循环的if语句的主体总是被执行( if条件始终为真)，那么它应该执行与第二个循环测试相同的次数。所以我不听你的推论。至于求和，要查找迭代次数，您需要添加以下内容：

• 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
2. if语句体(new_index=j)最多执行n次(n-1)/2次数--我们不知道确切执行了多少次，因为我们不知道A中的值是多少--所以我们不知道A[j] < A[i]的次数。它可以执行零次(考虑数组排序时的情况)。但是，我们通过假设条件总是真，找到了一个上界。在这种最坏的情况下，if语句的主体执行与内部for循环相同的次数--从前一个项目点开始执行的次数是n(n-1)/2
3. 通过类似的推理，另一个if语句体(执行交换的语句体)最多执行n次。

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