运行时气泡的/简单的排序

在课堂上，简单的排序被用作像我们的O（N）运行时的第一定义之一...运行时气泡的/简单的排序

但是，因为它通过每当它的阵列中的一个较少的迭代运行时，不会是沿着线的东西更多...

运行时气泡=总和（I = 0，N，（NI））？

而且不仅是运行一个又一个渐进分析这将是第N次迭代计算时最大的过程中，为什么被定义这种不O（N）？

1 + 2 + ... + N的总和是N*(N+1)/2 ...（高中数学）...并且接近(N^2)/2为N趋于无穷大。经典O(N^2)。

2011-10-31 13:11:16

我不知道，你（或你的教授）得到的概念，冒泡排序为O（n）。如果你的教授有保证O（n）的排序算法，他们会是明智的尝试和专利它:-)

冒泡排序，由它的本质，为O（n ）。

这是因为它必须完整地传递整个数据集才能正确放置第一个元素。

然后N - 1元件的第二通正确地放置的第二个。并且第三次通过N - 2元素正确放置第三个元素。

等等，有效地结束了接近N * N/2操作，这些操作，在除去多余0.5常数，是O（n 2 ）。

2011-10-31 13:10:11 paxdiablo

气泡排序的时间复杂度为O（n^2）。考虑复杂性时，只考虑最大表达式（但不考虑因素）

2011-10-31 13:12:18

回答