改进气泡排序的运行时间分析
改进气泡排序的运行时间分析
提问于 2012-09-20 16:00:32
我正在做一项家庭作业，在作业中，我被要求在一组大小为n的数据集上找到修改过的气泡排序所作的比较数量。要考虑的数据集是一个排序列表，其中交换第一个和最后一个元素，例如: 52341。以下是该算法的伪代码：
i <- n-1; new_i <- i
while i > 0 do
for j=1 to i do
if A[j] > A[j+1] do
A[j] <=> A[j+1]
new_i <- j
endif
endfor
i <- new_i - 1; new_i <- i
endwhileA是数据集，<=>是交换。
我试图找到一种方法来表示这个算法，将求和简化为给定类型数据集上的比较量的表达式。
不给出答案，有人能把我推向正确的方向吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-09-21 03:18:06
在Bubblesort实现中，比较的数量完全取决于输入的大小，即输入列表中元素的顺序并不重要。
如果您能够证明这一点(这并不困难)，那么计算N大小的输入列表的比较次数就足够了，因为我们已经表明顺序并不重要，这也相当容易：
我们有两个循环，外部while循环和内部for循环。外部循环从n到1(或n-1到0，但肯定不是从n-1到1，正如您的代码所建议的那样)，即我们有N次迭代。内环从1到i。
因此，我们在外循环的第一次迭代中有N个比较，第二次N-1中有N-1，第三次N-2中有N-2，N-N‘’th中有0。
我猜你是自己走这么远的。否则，你就完蛋了。
您的老师现在想看到的是，您知道以下公式，即所谓的“Gau sche Summenformel”，也称为"Gauss Sum"：
N+ (N-1) + (N-2) +.+(+1)+()= N^2/2 + N/2
所以你应该做的是：
- 显示比较的数量仅取决于输入的大小。
- 证明比较数等于N+ (N-1) + (N-2) +.+(N+1)+(N)
- 提到这与N^2/2 + N/2相同，指的是Gau先生。
;-)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12522600
复制相关文章
相似问题
社区富文本编辑器全新改版！诚邀体验～
全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验
腾讯云开发者
