冒泡排序 - 平均情况运行时复杂度的证明
所以，我在作业中遇到了这个问题，我尝试了几天来解决它，但我无法找到任何解决方案:(
鉴于增强的冒泡排序算法，平均运行时间是： 
而数组只包含 1 到 n 之间的数字，并且数组中的所有数字都彼此不同（给定公式中的“排列 i”是数组中数字的单个排列）数组，数组从0到n-1索引）
我需要证明公式中的平均运行时间是（n^2）的Big Omega，然后得出结论它也是（n^2）的Big Theta
我也知道当数字 1 位于第 k 个位置（k 介于 0 和 n-1 之间），算法至少执行 n*k 次操作
So, I've been given this question in my homework and I tried to solve it for a few days, but I can't reach to any solution :(
Given the enhanced Bubble Sort algorithm, the average runtime is:
whereas the array contains only numbers between 1 to n, and all the numbers in the array are different from each other (the "permutation i" in the given formula is a single permutation of the numbers in the array, array indexed from 0 to n-1)
I need to prove that the average runtime in the formula is Big Omega of (n^2), and then conclude that it is also Big Theta of (n^2)
I also know that when the number 1 is in the k position (k is between 0 and n-1), the algorithm performs at lesast n*k operations
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论