关于递推式T(n)=2T(n/2)+Θ(n)的紧界证明及相关疑问

嘿，这个问题问到点子上了——渐近紧界的证明核心就是同时满足上界（$O$）和下界（$\Omega$），咱们一步步理清楚：

首先先明确你的递推式：快排平均情况迭代后得到的$T(n) = nT(1) + n \log n$，这里$T(1)$是个固定常数（毕竟n=1时排序的时间是确定的，咱们记$c=T(1)$），所以式子可以简化为$T(n) = cn + n \log n$。

先回顾渐近记号的核心定义 #

要证明$T(n) = \Theta(n \log n)$，必须同时证明：

• $T(n) = O(n \log n)$（上界）
• $T(n) = \Omega(n \log n)$（下界）

第一步：证明$T(n) = O(n \log n)$ #

这个你已经有思路了，咱们再细化一下：
当$n \geq 2$时（取一个足够大的起始点），$\log n \geq 1$（不管是自然对数还是以2为底，对数的底数只会影响常数系数，不改变渐近阶），此时$cn \leq cn \log n$。
代入原式可得：
$$T(n) = cn + n \log n \leq cn \log n + n \log n = (c+1)n \log n$$
取常数$C = c+1$，$n_0=2$，完全满足$O(n \log n)$的定义：当$n \geq n_0$时，$T(n) \leq C \cdot n \log n$。

第二步：证明$T(n) = \Omega(n \log n)$ #

这是你疑惑的关键，其实也很直接：
我们需要找到常数$C>0$和$n_0$，使得当$n \geq n_0$时，$cn + n \log n \geq C \cdot n \log n$。
首先两边同时除以$n$（$n>0$，不改变不等式方向），得到：
$$c + \log n \geq C \cdot \log n$$
因为$c$是正数（排序时间不可能为负），我们可以直接取$C=1$，此时不等式变为$c + \log n \geq \log n$，这显然成立——毕竟正数加任何数都不会比原数小。
不过要注意$n=1$时$\log 1=0$，此时$T(1)=c$，而$1 \cdot \log 1=0$，所以咱们取$n_0=2$（当$n \geq 2$时，$\log n \geq 1>0$），此时$T(n) = cn + n \log n \geq n \log n$，完全符合$\Omega(n \log n)$的定义。

结论 #

既然$T(n)$同时满足$O(n \log n)$和$\Omega(n \log n)$，根据$\Theta$记号的定义，就可以得出$T(n) = \Theta(n \log n)$的紧界。

其实这里的线性项$cn$在渐近分析中是“次要项”，当$n$足够大时，主导项$n \log n$会远远超过线性项，所以它不会影响紧界的结论——这也是为什么快排平均情况的时间复杂度是紧的$\Theta(n \log n)$，而不仅仅是上界$O(n \log n)$。

备注：内容来源于stack exchange，提问作者mark