关于Tries和基数排序的效率问题

Question

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

编辑：快速排序及其竞争对手执行O(nlogn)比较；在最坏情况下，每个比较将花费O(k)时间（仅在检查的最后一位数字上不同）。因此，这些算法需要O(knlogn)的时间。按照同样的逻辑，平衡二叉搜索树操作需要O(klogn)的时间。

- Derek

Answer 1

大O符号不是这样使用的，即使对于基数排序k>=log n，O(kn)意味着如果n加倍，则处理时间将加倍，以此类推，这就是您应该使用大O符号的方式。

基数排序的一个优点是它的最坏情况是O(kn)(快速排序的O(n^2))，因此基数排序比快速排序更能抵抗恶意输入。如果使用位运算、以2为底数和原地msd基数排序，并使用插入排序处理较小的数组，则基数排序在实际性能方面也可以非常快。

同样的论点适用于trie树，它们在插入/搜索的最坏情况下是O(k)，在某种程度上可以抵御恶意输入。哈希表在O(1)的插入/搜索中进行哈希处理，但在最坏情况下的插入/搜索是O(N)。此外，trie树可以更有效地存储字符串。

请参阅Algorithmic Complexity Attacks。

- Nablamax

Answer 2

Radix排序的渐进时间复杂度为O(NlogN)，这也是快速排序的时间复杂度。Radix排序的优点在于它的最佳、平均和最差情况下的性能相同，而快速排序的最坏情况性能为O(N^2)。但是，它所需的空间是快速排序所需空间的两倍。因此，如果空间复杂度不是问题，则Radix排序是更好的选择。

- karn