algorithm - 算法的复杂性

Question

我正在阅读此页面 https://www.toptal.com/developers/sorting-algorithms他们想要关注的重点之一是这一点:

“表明最坏情况下的渐近行为并不总是选择算法的决定性因素。”

但是我认为它正在决定，因为根据数组的长度，一种类型可能比另一种更好，并且它的渐近线以图形方式显示。你怎么认为？谢谢

Answer 1

通常，对于某些问题，一种算法通常比另一种算法快，但在最坏情况下渐近变慢。具体来说，一种算法对于您正在处理的特定数据可能更快，即使在最坏的情况下它逐渐变慢。在某些情况下，内存使用也可能是一个问题。一个很好的例子是快速排序与归并排序。它们的平均运行时间都是 O(n log n)，但快速排序通常更快。然而，在最坏的情况下，快速排序的运行时间为 O(n^2)。此外，mergesort 传统上需要 O(n) 的额外内存。有一个就地变体，但我认为它要慢得多。另一个考虑因素是合并排序更容易并行化。

总而言之，算法的选择取决于您处理的数据、多线程能力和内存使用情况。