基数排序的时间复杂度是 O(kn)，其中 n 是要排序的键的数量，k 是键的长度。类似地，在 trie 中插入、删除和查找操作的时间复杂度为 O(k)。但是，假设所有元素都是不同的，不是 k>=log(n) 吗？如果是这样，这意味着基数排序的渐近时间复杂度为 O(nlogn)，与快速排序相同，而 trie 操作的时间复杂度为 O(logn)，与平衡二叉搜索树的时间复杂度相同。当然，常数因子可能有显着差异，但渐近时间复杂度不会。这是真的吗？如果是这样，基数排序和尝试比其他算法和数据结构有其他优势吗？
编辑：
Quicksort 及其竞争对手执行 O(nlogn)比较；在最坏的情况下，每次比较将花费 O(k) 时间（密钥仅在检查的最后一位数字处不同）。因此，这些算法需要 O(knlogn) 时间。按照同样的逻辑，平衡二叉搜索树操作需要 O(klogn) 时间。
大 O 表示法不是这样使用的，即使 k>=log n 用于基数排序，O(kn) 意味着如果 n 加倍，你的处理时间将加倍等等，这就是你应该如何使用 big-o 表示法。
基数排序的一个优点是最坏的情况是 O(kn)（快速排序的 O(n^2)），因此基数排序在某种程度上比快速排序更能抵抗恶意输入。就实际性能而言，它也可以非常快，如果您使用按位运算，以 2 的幂为基础，并针对较小的数组进行插入排序的就地 msd-radix 排序。
同样的论点对尝试有效，它们可以抵抗恶意输入，因为在最坏的情况下插入/搜索是 O(k)。哈希表在 O(1) 中执行插入/搜索，但使用 O(k) 散列并且在最坏的情况下 O(N) 插入/搜索。此外，try 可以更有效地存储字符串。
检查算法复杂性攻击
Radix排序的渐近时间复杂度为O(NlogN)，这也是Qucik排序的时间复杂度。基数排序的优点是它的最佳、平均和最坏情况性能相同，而快速排序的最坏情况性能为 O(N^2)。但它需要快速排序所需的两倍空间。所以，如果空间复杂度不是问题，那么基数排序是一个更好的选择。