基数排序基数值越低耗时越长及同基下数据量加倍耗时翻倍问题咨询

1. 基数值越低排序耗时越长的原因 #

• 基数排序的核心逻辑是多轮「分配+收集」操作，总时间复杂度为 O(d(n + k))*，各参数含义如下：
  • d：待排序元素按当前基数拆分得到的总位数
  • n：待排序元素的总数量
  • k：基数对应的桶数量，数值等于基数值
• 当待排序元素的最大值固定时（你的测试场景中最大值为2^25），d的计算公式为d = log_r M（r为基数值，M为元素最大值），基数值越小，需要遍历的总位数d越大：比如基数为2时需要处理25位，基数为4时仅需要处理13位，基数为8时仅需要处理9位。
• 虽然基数值越小对应的桶数量k越低，单轮桶操作的开销更小，但d增加带来的多轮全量元素遍历开销，远高于k降低节省的开销，最终表现为基数值越低总耗时越高，和你给出的测试数据趋势完全吻合。

2. 数据量翻倍耗时接近翻倍的原因 #

• 基数排序是典型的线性时间复杂度排序算法，当基数值固定、待排序元素的取值范围固定时，d和k都是固定常量，总耗时和元素数量n呈线性正相关。
• 你的测试中data2的元素数量是data1的2倍，对应三个基数的耗时比例分别为2.15、2.25、2.14，略高于2倍的差值来自桶初始化、临时内存分配等固定开销，整体完全符合线性时间复杂度的表现。

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