在这个网页上我可以读到:
一些特殊情况算法(Programming Pearls中提到了一个例子)可以比O(n*log(n))更快地对某些数据集进行排序.这些算法不是基于比较被排序的项目和依赖技巧.已经表明,没有密钥比较算法可以比O(n*log(n))更好地执行.
这是我第一次听说非比较算法.可能有人给我的那些算法中的一个例子,并更好地解释他们是如何解决的问题排序快于O(n日志(n))的？该网页的作者正在谈论什么样的技巧？
欢迎任何链接到论文或其他好的来源.谢谢.
首先,让我们直截了当地说明术语:
O(n logn).O(n logn).Bucket sort就是这样一个例子.为了给出第二类的直观示例,假设您知道输入数组完全由零和1组成.您可以迭代数组,计算零和1的数量.让我们称最后的计数n0和n1.然后迭代输出数组,写出n0零后跟n1一些.这是一种O(n)排序算法.
为这个问题提出线性时间算法是可能的,因为我们利用了数据的特殊结构.这与通用密钥比较算法形成对比.这样的算法不需要知道关于数据的任何信息,除了一件事:他们需要知道如何比较任何两个元素的排序键.换句话说,给定任何两个元素,他们需要知道哪个应该在排序数组中排在第一位.
能够使用一种算法以任何可想象的方式对任何事物进行排序的代价是,没有这样的算法可以希望比O(n logn)平均更好.