上周我偶然发现了这篇论文 作者在第二页提到的地方:
The last week I stumbled over this paper where the authors mention on the second page:
请注意,这会为整数边权重产生线性运行时间.
Note that this yields a linear running time for integer edge weights.
第三页相同:
这为整数边权重和基于比较的排序产生了 O(m log n) 的线性运行时间.
This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.
在第 8 页:
特别是,使用快速整数排序可能会大大加快 GPA.
In particular, using fast integer sorting would probably accelerate GPA considerably.
这是否意味着在特殊情况下对于整数值有 O(n) 排序算法?或者这是图论的专长?
Does this mean that there is a O(n) sorting algorithm under special circumstances for integer values? Or is this a specialty of graph theory?
附注:参考文献 [3] 可能会有所帮助,因为在第一页上他们说:
PS: It could be that reference [3] could be helpful because on the first page they say:
已对 [..] 图类实现了进一步改进,例如整数边权重 [3]、[...]
Further improvements have been achieved for [..] graph classes such as integer edge weights [3], [...]
但我无法访问任何科学期刊.
but I didn't have access to any of the scientific journals.
推荐答案是的,基数排序和计数排序是O(N).它们不是基于比较的排序,已被证明具有 Ω(N log N) 下界.
Yes, Radix Sort and Counting Sort are O(N). They are NOT comparison-based sorts, which have been proven to have Ω(N log N) lower bound.
准确地说,基数排序是O(kN),其中k是要排序的值的位数.计数排序是O(N + k),其中k是要排序的数字的范围.
To be precise, Radix Sort is O(kN), where k is the number of digits in the values to be sorted. Counting Sort is O(N + k), where k is the range of the numbers to be sorted.
在某些特定应用中,k 足够小,以至于基数排序和计数排序在实践中都表现出线性时间性能.
There are specific applications where k is small enough that both Radix Sort and Counting Sort exhibit linear-time performance in practice.
更多推荐
是否有 O(n) 整数排序算法?
发布评论