如何分析给定的优化冒泡排序的复杂度？
如何分析给定的优化冒泡排序的复杂度？
提问于 2013-05-09 22:27:38
这是一个优化冒泡排序算法的伪代码。我试图分析它的时间复杂度，但我不确定第4行的成本是多少(如果Ai-1 > Ai)。答案是(n-1)+(n-2)+........+1吗？另外，第5行到第8行的成本是多少？
1.for j = A.length to 2
2. swapped = false
3. for i = 2 to j
4. if A[i-1] > A[i]
5. temp = A[i]
6. A[i-1] = A[i]
7. A[i-1] = temp
8. swapped = true
9. if(!swapped)
10. break回答 1
Stack Overflow用户
回答已采纳
发布于 2013-05-09 22:32:27
单次迭代的第5行到第8行的成本为O(1)。
第3-8行的循环开销为O(j-1)。
在最坏的情况下，整个排序的成本是O((n-1) + (n-2) + ... + 2) = O(n^2) (当然，在最好的情况下，当数组已经排序时，成本只有O(n-1))。
顺便说一下，优化冒泡排序的实现包含一个错误:第9行的if应该在外部循环内，但在内部循环之外。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16464173
复制相关文章
相似问题
腾讯云开发者
