1

我是一名自学成才的计算机科学专业的学生。现在我正在阅读 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)。当 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。

在写这篇文章之前，我读了很多假设的解决方案，但没有一个能和我的一样。所以我想知道我的推理是否错误。

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

4

1 回答 1

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 < 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 次。

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

于 2017-08-24T07:09:02.497 回答