基数排序时间复杂度推导疑问：二进制位数为(logn)^(3/2)时

首先明确核心变量：

• $n$：待排序整数的总个数
• $m$：每个整数的二进制位数，题目给定 $m=(logn)^{3/2}$

基数排序的时间复杂度基础公式 #

基数排序的总时间由处理轮数和单轮时间开销共同决定：

• 若选择以 $2^r$ 作为基数（即每次处理 $r$ 位二进制数），则需要的处理轮数 $d = \lceil \frac{m}{r} \rceil$，可近似为 $\frac{m}{r}$（当 $m$ 能被 $r$ 整除时）。
• 每一轮依赖计数排序实现，计数排序的时间复杂度为 $O(n + k)$，这里 $k$ 是基数大小即 $2^r$，因此单轮时间开销为 $O(n + 2^r)$。

总时间复杂度公式可表示为：
$$T(n) = d \times O(n + 2^r) = O\left( \frac{m}{r} \times (n + 2^r) \right)$$

选择最优$r$值以最小化时间复杂度 #

我们需要找到合适的$r$平衡轮数和单轮开销：

• 若$r$过小，轮数$d$会增大，但$2^r$会缩小；
• 若$r$过大，轮数$d$会缩小，但$2^r$会急剧增大，导致单轮开销飙升。

这里选择 $r = logn$，此时：

1. $2^r = 2^{logn} = n$，单轮时间开销简化为 $O(n + n) = O(n)$；
2. 轮数 $d = \frac{m}{r} = \frac{(logn)^{3/2}}{logn} = (logn)^{1/2}$（即$\sqrt{logn}$）。

将结果代入总时间公式可得：
$$T(n) = O\left( (logn)^{1/2} \times n \right) = O(n \times (logn)^{0.5})$$

为什么这是最优解？ #

• 若$r < logn$，$2^r < n$，单轮时间仍为$O(n)$，但轮数会大于$(logn)^{1/2}$，总时间比$O(n\sqrt{logn})$更高；
• 若$r > logn$，$2^r > n$，单轮时间会变为$O(2^r)$，远大于$O(n)$，总时间会急剧上升。因此$r=logn$是最优选择。

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