1

这是一种使用 Quicksort 的分区算法在 n 元素数组中查找第 k 个最小数的算法。

    small(a,i,j,k)
     {
      if(i==j) return(a[i]);
      else
      {
      m=partition(a,i,j);
      if(m==k) return(a[m]);
      else
        {
         if(m>k) small(a,i,m-1,k);
         else small(a,m+1,j,k);
        }     
       }
     }

其中 i,j 是数组的开始和结束索引（ji=n（数组中的元素数）），k 是第 k 个最小的没有。我想知道上述算法的最佳情况和平均情况以及简要情况。我知道我们不应该在最好的情况下计算终止条件，并且分区算法也需要 O(n)。如果可能的话，我不想要渐近符号，而是精确的数学结果。

4

1 回答 1

2

首先，我假设数组是排序的——你没有提到的东西——因为否则该代码将无法工作。而且，在我看来，这就像一个常规的二进制搜索。

反正...

最好的情况是当数组只有一个元素时（你立即返回，因为 i == j），或者对于较大的 n 值，如果中间位置 m 与 k 相同；在这种情况下，不会进行递归调用，并且它也会立即返回。这使得它在最好的情况下为 O(1)。

对于一般情况，考虑 T(n) 表示使用您的算法解决大小为 n 的问题所花费的时间。我们知道：

T(1) = c

T(n) = T(n/2) + c

其中 c 是一个常数时间操作（例如，如果 i 与 j 相同，则比较的时间等）。一般的想法是，解决一个大小为 n 的问题，我们消耗一些常数时间 c（决定是否 m == k，如果 m > k，计算 m 等），然后我们消耗解决所花费的时间一半大小的问题。

扩展递归可以帮助您推导出一个通用公式，尽管这是 O(log(n)) 非常直观：

T(n) = T(n/2) + c = T(n/4) + c + c = T(n/8) + c + c + c = ... = T(1) + c*log (n) = c*(log(n) + 1)

那应该是确切的数学结果。该算法在 O(log(n)) 时间内运行。平均案例分析更难，因为您需要知道使用算法的条件。数组的典型大小是多少？k的典型大小？k 在数组中最可能的位置是什么？例如，如果它在中间，则平均情况可能是 O(1)。这真的取决于你如何使用它。

于 2013-09-21T15:55:34.387 回答