求O(nm/8 log(nm/8))+…+O(nm/m log(nm/m))的复杂度及推导方法

首先，我们知道快速排序（quicksort）的平均时间复杂度是O(x log x)，其中x是待排序元素的数量。你的算法对每个k∈[8, m]，处理x_k = nm/k个元素，所以每个子任务的时间是O( (nm/k) log(nm/k) )。总时间复杂度就是这些子任务的时间之和，即：

总时间 = O( Σ_{k=8}^m (nm/k) log(nm/k) )

接下来我们一步步拆解这个求和式：

步骤1：拆分对数项 #

利用对数的性质log(a/b) = log a - log b，可以把log(nm/k)拆成log(nm) - log k，代入求和式后得到：

Σ_{k=8}^m (nm/k)(log(nm) - log k) = nm·log(nm)·Σ_{k=8}^m 1/k - nm·Σ_{k=8}^m (log k)/k

现在我们分别分析这两个求和项的量级：

步骤2：分析第一个求和项——调和级数部分 #

第一个求和是Σ_{k=8}^m 1/k，这是调和级数的一部分。调和级数的前m项和H_m = Σ_{k=1}^m 1/k满足H_m ≈ ln m + γ（其中γ≈0.577是欧拉常数），所以从k=8到m的和就是H_m - H_7。当m足够大时，H_7是常数，所以这个求和的量级是O(log m)。

因此第一个部分的整体量级是：

nm·log(nm)·O(log m) = O(nm·log(nm)·log m)

步骤3：分析第二个求和项——对数与倒数的乘积和 #

第二个求和是Σ_{k=8}^m (log k)/k，我们可以用积分近似来估算它的量级。考虑函数f(x) = (ln x)/x，它在x≥1时的求和可以用积分上下界来估计：

∫_{8}^{m+1} (ln x)/x dx ≤ Σ_{k=8}^m (log k)/k ≤ ∫_{7}^{m} (ln x)/x dx

计算积分∫(ln x)/x dx = (ln x)²/2 + C，代入上下界后得到这个求和的量级是O( (log m)² )。

因此第二个部分的整体量级是：

nm·O( (log m)² ) = O(nm·(log m)² )

步骤4：比较两个部分的量级 #

现在对比两个部分的量级：

• 第一部分：O(nm·log(nm)·log m)，而log(nm) = log n + log m，所以这部分也可以写成O(nm·(log n + log m)·log m) = O(nm·log n·log m + nm·(log m)²)
• 第二部分：O(nm·(log m)² )

显然，当n≥2（实际算法中n肯定不会太小），nm·log n·log m的量级要大于nm·(log m)²，所以第一部分是主导项。

最终结论 #

你的算法的总时间复杂度是O(nm·log(nm)·log m)，或者也可以等价写成O(nm·(log n + log m)·log m)，两者是等价的。

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