algorithm - 通过快速排序方法查找分区的时间复杂度

Question

这是一个使用快速排序的分区算法在 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 是数组的开始和结束索引(j-i=n(数组中的元素数))，k 是要找到的第 k 个最小的 no。我想知道什么是最佳情况，上述算法的平均情况以及简要情况。我知道我们不应该在最好的情况下计算终止条件，而且分区算法也需要 O(n)。如果可能的话，我不想要渐近符号，而是精确的数学结果。

Answer 1

首先，我假设数组已排序 - 您没有提到 - 因为该代码否则无法工作。而且，嗯，这在我看来就像是常规的二进制搜索。

无论如何...

最好的情况是数组只有一个元素长(你立即返回因为 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)。这实际上取决于您如何使用它。