Big O计算一个数据集大小(n)相对于运行时间的上限。
O(n*log(n))的算法并不总是比O(n^2)算法更快,但在考虑最坏情况时,它很可能更快。当你复制工作集(最坏情况)时,O(n^2)算法需要大约4倍的时间,而O(n*log(n))算法则需要更少的时间。数据集越大,使用O(n*log(n))算法通常会更快。
编辑:感谢'harms',我将纠正第一次回答中的错误陈述:我说在考虑最坏情况时O(n^2)总是比O(n*log(n))慢,这是错误的,因为两者都是除了一个常数因子之外相同!
例如:假设我们有最坏情况,我们的数据集大小为100。
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 = 200 (使用log_10)
问题在于两者都可以乘以一个常数因子,比如我们把后面那个乘以c,结果就是:
O(n^2) --> 100 * 100 = 10000
O(n*log(n)) --> 100 * 2 * c = 200 * c (使用log_10)
因此,对于c > 50,我们得到O(n*log(n)) > O(n^2),n=100。
我必须更新我的声明:对于每个问题,在考虑最坏情况时,O(n*log(n))算法将比O(n^2)算法更快,对于任意大的数据集。
原因是:c的选择是任意的但是常数。如果你增加数据集足够大,它将支配每个c的常数选择的影响,并且当讨论两个算法时,两者的c都是常数!