上周我偶然发现了这篇论文,作者在第二页提到:
请注意,这会产生整数边权重的线性运行时间.
第三页上的内容相同:
这产生整数边缘权重的线性运行时间和基于比较的排序的O(m log n).
在第8页:
特别是,使用快速整数排序可能会显着加速GPA.
这是否意味着在特殊情况下存在整数值的O(n)排序算法？或者这是图论的专长？
PS:
可能参考文献[3]可能会有所帮助,因为在第一页上他们说:
[...]图表类已经实现了进一步的改进,例如整数边权重[3],[...]
但是我无法访问任何科学期刊.
如果我使用splice()从数组中删除一个元素,如下所示:
arr.splice(i, 1);
这是O(n)不是最糟糕的情况,因为它会在我之后移动所有元素？或者它是不变的时间,下面有一些链表魔术吗？