big-o - 关于try和基数排序的效率

Question

基数排序的时间复杂度为 O(kn)，其中 n 是要排序的键的数量，k 是键的长度。同样，在 trie 中插入、删除和查找操作的时间复杂度是 O(k)。但是，假设所有元素都是不同的，不是 k>=log(n) 吗？如果是这样，那就意味着基数排序的渐近时间复杂度是 O(nlogn)，等于快速排序的时间复杂度，而 trie 运算的时间复杂度是 O(logn)，等于平衡二叉搜索树的时间复杂度。当然，常数因子可能会有很大差异，但渐近时间复杂度不会。这是真的吗？如果是的话，与其他算法和数据结构相比，基数排序和尝试是否具有其他优势？

编辑:

Quicksort 及其竞争对手执行 O(nlogn) 次比较；在最坏的情况下，每次比较都将花费 O(k) 时间( key 仅在最后检查的数字处不同)。因此，这些算法需要 O(knlogn) 时间。按照同样的逻辑，平衡二叉搜索树操作需要 O(klogn) 时间。

Answer 1

Big O notation 不是那样使用的，即使 k>=log n 用于基数排序，O(kn) 意味着如果 n 加倍，你的处理时间将加倍等等，这就是你应该如何使用 big-o符号。

基数排序的一个优点是它的最坏情况是 O(kn)(快速排序的 O(n^2))，因此基数排序在某种程度上比快速排序更能抵抗恶意输入。它在实际性能方面也可以非常快，如果您使用按位运算，以 2 的幂为基础，并使用插入排序对较小的数组进行就地 msd-radix 排序。

相同的论点对尝试有效，它们可以抵抗恶意输入，因为插入/搜索在最坏的情况下是 O(k)。哈希表在 O(1) 中执行插入/搜索，但使用 O(k) 哈希，在最坏的情况下 O(N) 插入/搜索。此外，尝试可以更有效地存储字符串。

检查 Algorithmic Complexity Attacks