算法复杂度与现实生活的关系？

Question

我的问题是关于理论和实践的问题。

例如，我想对一个数字列表进行排序。Mergesort的复杂度为O(n*logn)，而bubblesort的复杂度为O(n^2)。这意味着合并更快。但复杂性并没有考虑到发生在电脑上的所有事情。我的意思是，例如，合并是一种分而治之的算法，它所需的空间比短的要大。那么，创建这个额外的空间和使用资源(传输数据、填充代码指令等)比不使用任何额外空间的bubblesort花费更多的时间，难道不可能吗？对于一定长度的输入(可能很小)，使用复杂度更差(“更大”)的算法不可能比另一种算法更有效吗？

Answer 1

答案是肯定的。

一个典型的例子是插入排序是O(n^2)。然而，高效的排序实现通常切换到大约只剩下100个元素的插入排序，因为插入排序确实很好地利用了缓存，并且避免了CPU中的管道阻塞。不，插入排序不会缩放，但它的性能优于。

我要说的是，可伸缩性就像一辆Mack卡车。你想把它装得满满的，但在当地的杂货店购物可能不是最好的选择。

Answer 2

算法复杂性只告诉您，当输入越来越大，即接近无穷大时，两种算法将如何进行比较。它没有告诉你他们将如何比较较小的输入。要确定这一点，唯一的方法就是对代表典型情况的数据和设备进行基准测试。