知识卡片
位数和基数要一起计入成本
若每个元素有p个digit、基数k,每轮稳定计数成本O(n+k),总计O(p(n+k))。增大k通常减少p,却扩大计数数组及每轮初始化;不能只看循环轮数,也不能不计k就称任何情况都线性。
225以128位数据作模型,按原上标修正后的规模表达式为:
| n | k | p | n log₂n | p(n+k) |
|---|---|---|---|---|
| 2²⁰ | 2¹⁶ | 8 | 20,971,520 | 8,912,896 |
| 2¹⁰ | 2¹⁶ | 8 | 10,240 | 532,480 |
| 2¹⁰ | 2⁸ | 16 | 10,240 | 20,480 |
原文小规模快排式误写2²⁰×10;最后基数2⁸的表达式/8160也错误,应为16×1024+16×256=20480,因此不能得到其“略快”结论。两列只是忽略各自常数的模型量,不是真实耗时或精确倍速;当前rxsort仅处理int,也不直接实现128位记录。
219接口保留n、p、k三参数依赖;p必须足以覆盖所需有效位,k和数据域需让数字索引合法,不能只选p=1就宣称全键已排序。
220实际pval=(int)pow(k,n)。需基数/指数使结果可准确、可表示且非零,数据为允许非负域;浮点幂转int与除模并不自动对任意参数安全。逐轮空间重用counts/temp,辅助O(n+k)。
225原XHTML全部指数已核对,完整三情形修正表已在成本卡保留:小规模最后一例应20480而非8160,不能把省略不同常数的模型量当精确倍速。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 位数和基数要一起计入成本
- · 基数排序的接口定义
- · 基数排序的实现与分析
- · 问与答
原书出处 · 4 处
- · 查看原书依据
pn+pk最小化。(其中p为每个元素的位数,n为元素的个数,k为基数)。一般情况下,通常使k小于等于n。
- · 查看原书依据
O(pn+pk),n为要排序的元素的个数,k为基数,p为位的个数。
- · 查看原书依据
幂运算和模运算。这对于整数来说特别有效,但不同的数据类型需要使用不同的方法。有一些方法可能需要考虑机器具体细节,例如字节顺序和字对齐。 图 12-7 用基数排序对十进制整数进行排序 毫无疑问,基数排序的时间复杂度取决于它选择哪种稳定排序来对位数值进行排序。由于基数排序对每个p位置的位数值使用计数排序
- · 查看原书依据
128位的元素要进行排序。如果使用快速排序效率如何?如果使用基值为216的基数排序效率如何?哪种方法效率更高?假设元素的个数是210而不是220,那么快速排序和基数排序的表现又会如何? 答:用快速排序需要O(nlg n)=220×20=2.10×107乘以一段固定时间。把元素看做基数为216的数值,