首先得理清这个函数的核心逻辑：它用分治思路计算数组区间的几何平均值，但有个很关键的点——每次递归处理子问题前，都会对当前区间执行一次quicksort（已知常规quicksort的时间复杂度是O(n log n)，n为当前区间的元素个数）。

建立时间复杂度递推式 #

我们设T(n)为处理包含n个元素的区间所需的时间（n = r - l + 1）：

• 当n = 0（r < l）或者n = 1（r = l）时，只做常数级的判断和返回操作，所以T(0) = O(1)，T(1) = O(1)
• 当n > 1时，函数会先花O(n log n)的时间排序，然后递归处理两个大小约为n/2的子区间，总耗时是2*T(n/2)。因此递推式可以写成：

  T(n) = 2*T(n/2) + O(n log n)
  

求解递推式（递归树法） #

我们用递归树来展开计算这个递推式：

• 根节点的代价是n log n（第一次排序的时间）
• 第二层有2个节点，每个节点处理n/2个元素，各自排序的代价是(n/2) log(n/2)，这一层的总代价是2*(n/2 log(n/2)) = n(log n - 1)
• 第三层有4个节点，每个处理n/4个元素，总代价是4*(n/4 log(n/4)) = n(log n - 2)
• 以此类推，每往下一层，总代价里的减数就加1，直到叶子节点（每个节点处理1个元素，代价为O(1)），整个递归树一共有log₂n层

把所有层的代价加起来：

总代价 = n*(log n * log n) - n*(0 + 1 + 2 + ... + (log n - 1))

其中0+1+...+(log n -1)是等差数列求和，结果为(log n)*(log n -1)/2。代入后化简可以得到，总代价的渐进紧界是Θ(n (log n)²)，对应的渐进上界就是O(n (log n)²)。

最终结论 #

geometric递归函数的时间复杂度为O(n (log n)²)（或者更精确的Θ(n (log n)²)）。

内容的提问来源于stack exchange，提问作者Carlota Medeiros