sail007love1 2020-02-22 09:44 采纳率: 0%
浏览 724

求解:算法设计与分析题

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

考虑下面的算法:

输入: 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) 可以用Θ记号来表示算法的运行时间吗?请说明。

  • 写回答

1条回答 默认 最新

  • threenewbee 2020-02-22 11:10
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名