复杂性帮助.O(n ^ 2),0(nlog)等

Question

嘿,有人可以帮我确定复杂性吗？我班上给出的一个例子是

泡泡排序

int main() {
   int a[10] = {10,9,8,7,6,5,4,3,2,1};
   int i,j,temp;

   for (j=0;j<10;j++) {
      for (i=0;i<9;i++) {
         if (a[i] > a[i+1]) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
         }
      }
   }
   for (i=0;i<10;i++) {
      printf("%d ",a[i]);
   }
}

其复杂度为O(n ^ 2),因为它有两个O(n)循环,因此O(n)x O(n).

---

并且他们说quicksort的复杂度为O(nlog(n))..为什么会这样？

是因为它围绕一个循环划分一个数字？

-谢谢

Answer 1

没有快速的一句话解释.在最坏的情况下,快速排序实际上是O(n ²),但它平均为O(n log n),所以如果你试图分析它,你将无法证明它总是O(n log n).它平均只有O(n log n),在所有可能的数据集中取平均值.对于任何特定的列表,它可能会更糟.

如果枢轴最终真的非常糟糕,那么快速排序将会非常糟糕.这可能发生在已排序的数据上,例如,如果您始终在数组的开头或结尾选择固定元素作为pivot元素.

另一方面,其他排序算法(如合并排序和堆排序)始终为O(n log n).他们没有病态的情况,他们的表现会降低到O(n ²).如果你想要的是始终如一的可预测的性能,这使它们成为可取的.快速排序的优点是总体上算法平均速度更快,但并非总是如此.

编辑:的确,正如@pst所说,合并排序在排序数组时需要O(n)空间(合并的临时空间),这不太理想.这是反对它的观点.但是,另一个反对快速排序的观点是它是一种不稳定的排序.在排序之后,可以混洗彼此相等的元素.

Timsort是一个非常棒的新搜索算法 - 好吧,不那么新,更多是现有算法的完美组合加上大量的微调和聪明的优化(奔腾的事情就是金钱).阅读该文本文件,一瞥Great Programming.