为什么Bubble，Insertion和Selection排序有相同的Big-O？

正如标题所问，为什么插入，泡沫和选择排序有相同的大 - ？在我的算法类中，我们已经介绍了上述四种算法并合并排序，为什么还要使用上述算法中的任何一种来代替合并排序？为什么Bubble，Insertion和Selection排序有相同的Big-O？

来源

2012-12-16 user123

我不确定你在这个问题上得到什么。你是否想知道这些算法有什么共同之处，使它们都具有相同的复杂性，或者你想知道为什么复杂性不是别的？ –

你在这里问两个不同的问题1）为什么是泡沫，插入和选择O（n^2）和2）什么是他们的有效用例？经过独立研究后，请将这些分开。投票结束的过于宽泛。 – djechlin

虽然它们是不同的算法，但它们具有相同的渐近复杂性，因为在某个级别上，每个算法都会在长度为n的列表中进行两次通过。关键是Big-O是一种最糟糕的绩效衡量标准。插入排序在最坏的情况下是O（n^2），但是在最好的情况下，当列表已经排序时，它变成O（n）。不同的排序算法具有不同的优势，需要分析超越大的复杂性。这就是说，你几乎总是使用nlog（n）排序更好，而像泡泡排序这样的主要功能可能会将人们引入排序算法的概念。

来源

2012-12-16 04:09:52 Chris

事实上，插入/选择排序在实践中是非常有用的，在将“小”数组作为递归O（logn）排序的基本情况时使用，因为一旦n足够小，它们实际上更快 – Bwmat

当N可以适应本地缓存（当N很小时）可以使用插入排序。在TimSort中使用类似的思想，它是n log n，直到N变小，然后切换n^2算法。 – Justin

尽管一些排序算法如冒泡排序对于大量项目来说非常缓慢，但当您只有少量项目时它们非常快，部分原因是它们非常简单。当物品已经接近正确位置时，泡泡分类或插入排序也可能很有用。通常情况下，一个好的排序算法将使用一种技术来获取按课程级别排序的项目，然后使用另一种算法来进行精细排序。

来源

2012-12-16 04:13:03

这是在这里被问到的一个更常见的问题。 Big-O符号是衡量算法理论界限的一种方法，这就是在最佳情况下使事物保持恒定时间O（1）的一种方法，即使这种情况很少发生，因此也是最好的情况。这三种算法具有相同的大O的原因是它们都以相同的方式攻击排序问题，具有相同的大O并不意味着这些算法在工作方式上是远程等价的，即使过程是相似的。从纯粹的学术角度来看，这些教授的理由是，你可以从历史中学习，而不是认为你会冒泡沫排序来“震惊世界”。它也被用来表明看起来像一个简单的概念，即排序，可以证明远比“天真”的方法会产生更复杂。

来源

2012-12-16 04:15:09 Woot4Moo

措辞非常好，谢谢。 – user123

为什么Bubble，Insertion和Selection排序有相同的Big-O？

回答

相关问题