我对这个话题有点困惑。
如果列表已经排序，那么我们说最好的性能是 n。
对于一些算法，比如冒泡排序，我们说最坏的情况是 n^2。
我的困惑是为什么我们说它的 n^2？那个广场是怎么来的？我们保持正方形的假设是什么？为什么我们不像 O(1), O(log n), O(n), O(2^n) 那样给出它？请帮助我理解这些术语......文章，博客，讲义......任何会有所帮助。
我是初学者。
问问题
209 次
5 回答
0
O(n^2) 意味着算法（冒泡排序）在最坏的情况下必须进行 n^2 次比较（大于、小于、等于），其中 n 是被排序的项目数。
于 2013-04-30T01:18:30.630 回答
0
很多答案很多文字（有些很棒）
但对于愚蠢的人来说不是一个足够简单的答案，
所以我尝试一下：
在： 0,3,7,8 ... n=4 最佳情况
1. 0,3 ,7,8
2. 0, 3,7 ,8
3. 0,3, 7,8
- 没有发生任何变化它的排序... O(n-1) -> ~O(n)
在： 8,7,3,0 ... n=4 最坏情况
1. 7,8 ,3,0
2. 7, 3,8 ,0
3. 7,3, 0,8
- 发生变化还没有停止
4. 3,7 ,0,8
5. 3, 0,7 ,8
6. 3,0, 7,8
- 发生了变化所以不要停止
7. 0,3 ,7,8
8. 0 , 3,7 ,8
9. 0,3, 7,8
- 没有发生变化，所以它的排序... O((n-1)^2) -> ~O(n^2)
希望我没有在某个地方犯下愚蠢的错误……它当然可以帮助某人。
于 2013-10-29T11:58:04.920 回答
0
于 2013-04-30T05:47:40.887 回答
0
假设我们有以下简单的程序，我们想找到它的时间复杂度。
return_sum(n)
{
y=4
while(n>0)
{
y=y+y
n=n-1
}
return y
}
计算机程序由一组步骤组成，程序的时间复杂度可以认为是程序解决特定问题所采取的步骤数。
return_sum() 程序所需的步骤数：
return_sum(n)
{
y=4 // this step will take constant time say, c1, and will run only once
while(n>0) //this step run n time , if step takes c2 time , total time is n * c2
{
y=y+y // this step will run n-1 time , total time (n-1) * c3
n=n-1 // this step will run n-1 time , total time (n-1) * c4
}return y // takes constant time c5, run once.
}
让我们添加执行此程序的所有步骤所花费的时间
= c1 + n * c2 + (n-1) * c3 + (n-1) * c4 +c5
= n(c2 + c3 + c4 ) + (c1+ c5 - c2 - c3)
其中 (c2 + c3 + c4 ) 和 (c1+ c5 - c2 - c3) 是常数，我们可以将它们表示为 a 和 b 。
=an + b
这是 n 的函数，
f(n) = an+b
这个函数是O(n)。所以这个程序的时间复杂度是O(n)。
证明：
f(n) = an+b
Lets give a and b any constant values , suppose a = 100 and b = 200
Now for all sufficient large value of n >=1.
100n < 200n
and
200 < 200n
f(n)=100n+200 < 200n + 200n
< 400n
< 400 * n where c = 400 and n0 = 1
f(n)= O(n)
类似地，当我们在插入排序中添加所有步骤时，我们得到 f'(n)，即
f'(n) = an^2+bn+c
通过以上证明我们可以很容易地发现 f'(n) = O(n^2)
于 2013-04-30T12:49:01.437 回答
0
要理解冒泡排序（或任何排序，真的），您需要仔细考虑它使用的过程。例如，冒泡排序通过扫描整个列表，交换不合适的对来工作。在最坏的情况下，它会在第一遍进行 n - 1 次交换，检查所有 n 个元素。对于第二遍，保证最后一个元素是有序的——因为它会“冒泡”到最后。因此，排序最多必须进行 n - 2 次交换，检查 n - 1 个元素，等等。因此，最坏的情况是 O(n^2)。
如果你能理解排序是如何工作的，那么你就可以计算出最好和最坏的情况。您可以从 Wikipedia 开始：
http://en.wikipedia.org/wiki/Sorting_algorithm
PS——冒泡排序几乎是有史以来最糟糕的排序。但是，如果您对已排序的数据进行排序，它的性能会比其他方法更好。
于 2013-04-30T01:13:19.830 回答