求解：算法设计与分析题

Question

求解各位大神，能详细解答下，不只是答案，谢谢了。

考虑下面的算法：

输入： n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n)
2. {
3. int j,i,sorted;
4. i=sorted=0;
5. while(i<n-1 && !sorted) {
6. sorted=1;
7. for(j=n-1;j>i;j--) {
8. if(A[j]<A[j-1]) {
9. temp=A[j];
10. A[j]=A[j-1];
11. A[j-1]=temp;
12. sorted=0;
13. }
14. }
15. i=i+1;
16. }
17. }

（1） 算法所执行的元素比较次数最少是多少次？什么时候达到最少？

（2） 算法所执行的元素比较次数最多是多少次？什么时候达到最多？

（3） 算法所执行的元素赋值次数最少是多少次？什么时候达到最少？

（4） 算法所执行的元素赋值次数最多是多少次？什么时候达到最多？

（5） 用О、和Ω记号表示算法的运行时间。

（6） 可以用Θ记号来表示算法的运行时间吗？请说明。

Answer 1

最少比较n-1次，当数组本身就是有序的时候最少
最多比较n * (n-1)/2次，当数组逆序的时候最多
最少交换0次，当数组本身就是有序的时候
最多交换n * (n-1)/2次，当数组逆序的时候
O(n)=n^2
Ω(n)=1
Θ(n)=n^2