冒泡/简单排序的运行时间
在课堂上，简单排序的使用就像我们对 O(N) 运行时的第一个定义一样......
但是由于它每次运行时都会对数组进行一次更少的迭代，所以它不是更符合以下方式吗...
运行时气泡= sum(i = 0, n, (ni)) ？
而且，在渐近分析中，不仅是一个接一个地运行的最大进程才被计为 N 次迭代，为什么根据定义，这种排序不是 O(N) 呢？
In class, simple sort is used as like one of our first definitions of O(N) runtimes...
But since it goes through one less iteration of the array every time it runs, wouldn't it be something more along the lines of...
Runtime bubble= sum(i = 0, n, (n-i)) ?
And aren't only the biggest processes when run one after another counted in asymptotic analysis which would be the N iteration, why is by definition this sort not O(N)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
1 + 2 + ... + N的总和是N*(N+1)/2...（高中数学）...并且接近(N^2)/2随着N趋于无穷大。经典O(N^2)。The sum of
1 + 2 + ... + NisN*(N+1)/2... (high school maths) ... and that approaches(N^2)/2asNgoes to infinity. ClassicO(N^2).我不确定你（或你的教授）从哪里得到冒泡排序是 O(n) 的概念。如果您的教授拥有一个有保证的 O(n) 排序算法，那么他们明智的做法是尝试并为其申请专利:-)
从本质上讲，冒泡排序是 O(n2 ）。
这是因为它必须完整传递整个数据集，才能正确放置第一个元素。
然后第二遍
N - 1元素以正确放置第二个。第三遍N - 2元素以正确放置第三个。依此类推，实际上最终得到了接近
N * N / 2次操作，删除了多余的0.5常量，复杂度为 O(n2 ）。I'm not sure where you (or your professor) got the notion that bubble sort is O(n). If your professor had a guaranteed O(n) sort algorithm, they'd be wise to try and patent it :-)
A bubble sort is, by it's very nature, O(n2).
That's because it has to make a full pass of the entire data set, to correctly place the first element.
Then a second pass of
N - 1elements to correctly place the second. And a third pass ofN - 2elements to correctly place the third.And so on, effectively ending up with close to
N * N / 2operations which, removing the superfluous0.5constant, is O(n2).冒泡排序的时间复杂度为O(n^2)。
考虑复杂度时，只考虑最大的表达式（而不考虑因子）
The time complexity of bubble sort is O(n^2).
When considering the complexity, only the largest expression is considered (but not the factor)