嘿，有人可以帮我确定复杂性吗？我课堂上给出的一个例子是
冒泡排序
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)。
他们说快速排序的复杂度为 O(nlog(n)) .. 为什么会这样？
是因为当它绕过一个循环时，它会除以一个数字？
-谢谢
没有快速的一句话解释。快速排序在最坏的情况下实际上是 O( n 2 )，但平均是 O( n log n )，所以如果你尝试分析它，你将无法证明它总是 O( n log n )。在所有可能的数据集中平均只有 O( n log n ) 。对于任何特定的列表，它可能会更糟。
如果枢轴最终变得非常非常糟糕，那么快速排序的表现将非常糟糕。这可能发生在已排序的数据上，例如，如果您始终选择数组开头或结尾的固定元素作为枢轴元素。
另一方面，其他排序算法，如归并排序和堆排序，总是 O( n log n )。他们没有表现下降到 O( n 2 ) 的病态案例。如果您希望始终保持一致、可预测的性能，这将使它们更受欢迎。快速排序的优点是总体上平均来说是一种更快的算法，但并非总是如此。
编辑：确实，正如@pst所说，合并排序在对数组进行排序时需要 O( n ) 空间（合并的临时空间），这不太理想。这是反对它的一点。但是反对快速排序的另一点是它是一种不稳定的排序。排序后彼此相等的元素可能会被打乱。
Timsort是一个很棒的新搜索算法——嗯，不那么新，更多的是现有算法的完美组合，加上大量的微调和巧妙的优化（疾驰的东西就是钱）。阅读该文本文件以了解 Great Programming。
Big-O notation is simply a relationship between the input value (number of elements in your case) and the complexity (time complexity in your case, van also be space complexity).
You're correct about the bubble sort. Because it loops n times inside another loop of n times, the time complexity is O(n2).
Quicksort is slightly different. It does a number of passes which depends on n but, in each case, it manages to put all the values lower than the midpoint on the "left" and all values higher than the midpoint on the "right" - both halves are still unsorted but you know that the all the left elements are less than any of the right elements (let's call this the pivot rule).
This basically chops the workload in half for each sub-loop which leads to average case O(log n). Similar to binary search or balanced trees, any algorithm that divides the workload by a factor for each iteration is O(log n).
Combining the two gives you O(n log n).
This wikipedia page actually shows a nice little graphic on the top right that shows quicksort in action. Since a picture is worth a thousand words (and an animation is worth a thousand pictures), you should look at that for a while to understand.
You'll see that it first divides the workspace in two then swaps elements between the two halves until the pivot rule is met.
Because the workload is divided into two totally separate independent areas, quicksort is ripe for parrallel processing with no resource contention. Provided you have enough processors, as soon as you've partitiond the data into two areas, you can give each area to a separate processor for further partitioning. This is not possible with bubble sort since that sort doesn't give you two independent areas.
Actually quicksort is O(n log(n)) in the average case. In the worst case you pick the largest or smallest element as the partition every time and do n + (n -1) + ... 1 = O (n ^ 2).
In the best case (the average case works out to the same big-O) you do n comparisons for the first partition. This makes two calls on problems of size n / 2 and those calls take n / 2 comparisons to partition. This continues so you get n + 2 * (n / 2) + 4 * (n /4) + ... . There are log(n) total terms and each one is n so the whole thing is O(n*log(n)).
As Thon said you can get the same result by applying Master's theorem, but it's probably worth your time to do some examples by hand.
参见Wikipedia 上的分析。
前面的答案很好地描述了快速排序及其运行时间，但我想评论最坏情况下的运行时间。
确实，在平均情况下（给定输入的随机排列），快速排序通常为 O(n log n)，在最坏的情况下为 O(n^2)。但是，快速排序通常不会在每一步指定要围绕哪个元素进行分区，因此当您选择任何元素（通常是第一个或最后一个）作为枢轴时会出现 O(n^2) 情况，而不考虑其与列表中的其他元素。
您可以通过明智地选择枢轴来实现快速排序以在最坏情况下运行 O(n log n)。一种方法是在 O(n) 时间内找到中位数。（参见http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22）然后，如果您总是围绕中位数进行分区，则检查任何元素的次数最多为 O(log n)，因此总运行时间为 O(n log n)。
快速排序是递归的。只需写出伪代码，您就可以轻松推导出每次重复运行时间的递归公式，然后使用主定理得出最终答案。
Contrary to the opinion of all people here, the complexity of your program is O(1). You haven't defined what n is. I know, my answer seems a bit daft, but in practice it is often more important to find the bounds of your problem than the complexity of the algorithm. If your dataset will never be bigger than a given size, you may better use a simpler method which has good enough performance/behaviour.