排序算法证明和运行时

Question

Hydrosort 是一种排序算法。下面是伪代码。

*/A is arrary to sort, i = start index, j = end index */

    Hydrosort(A, i, j):                 // Let T(n) be the time to find where n = j-1+1

      n = j – i + 1                              O(1)
      if (n < 10) {                              O(1)
        sort A[i…j] by insertion-sort            O(n^2) //insertion sort = O(n^2) worst-case
        return                                   O(1)
      }
      m1 = i + 3 * n / 4                         O(1)
      m2 = i + n / 4                             O(1)
      Hydrosort(A, i, m1)                        T(n/2)
      Hydrosort(A, m2, j)                        T(n/2)
      Hydrosort(A, i, m1)                        T(n/2)

T(n)=O(n^2)+3T(n2)，所以T(n)是O(n^2)。 我用主定理的第3种情况来解决这个递推。

我有2个问题。

1. 我计算的最坏情况下的运行时间是否正确？

2. 我如何证明Hydrosort(A，1，n)能正确地对n个元素的数组A进行排序？

Answer 1

我在这里正确计算了最坏情况下的运行时间吗？

恐怕没有！复杂性函数是。

T(n) = 3T(3n/4) + CONST

这是因为：

1. 你有三个递归调用的大小问题 3n/4
2. 这里的常数修饰语是 O(1)，因为所有的非递归调用操作都被限定为一个常数大小（具体来说，n<=10的插入排序是 O(1)).

如果你继续计算你会变得更糟糕 O(n^2) 复杂性

如何证明Hydrosort(A，1，n)能正确地对一个有n个元素的数组A进行排序？

通过归纳。假设你的算法适用于大小为 n，让我们来研究一个大小问题 n+1. 对于 n+1<10 是琐碎的，所以我们忽略这种情况。

• 在第一次递归调用后，你可以保证array的前34个元素被排序，特别是你可以保证前n4个元素是这部分中最小的元素，这意味着，它们不可能在数组的最后n4个元素中，因为至少有n2个元素比它们大。这意味着，它们不可能在数组的最后n4中，因为至少有n2个元素比它们大。这意味着，n4个最大的元素在m2和j之间。
• 在第二次递归调用后，由于保证会在n4个最大的元素上调用，所以会将这些元素放在数组的最后。这意味着m1和j之间的部分现在被正确排序了。这也意味着，3n4个最小的元素在i和m1之间。
• 第三次递归调用对3n4个元素进行了正确的排序，n4个最大的元素已经到位，所以数组现在已经排序了。