问用快速排序法求分区的时间复杂度

EN

首先，我假设数组是排序的--这是你没有提到的--因为这段代码不能正常工作。在我看来，这就像是一个常规的二进制搜索。

不管怎样..。

最好的情况是，当数组只有一个元素长(您立即返回，因为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在数组中的mos可能位置是什么？例如，如果它在中间，那么平均情况可能是O(1)。这真的取决于你如何使用它。