小白菜*** 2022-03-05 11:54 采纳率: 100%
浏览 39
已结题

提问关于时间复杂度计算

算法分析题,阅读以下代码:

int a[100];

Fun(int a[], int n)

{

for(int i=1; i<=n; ++i)

{

    cin>>a[i];

}

int K=1;

for(int i=1; i<=n; ++i)

{

    if(i > 1 && a[i] < a[i - 1])

    K = i;

    while (K < n && a[i] >= a[K +1])

        ++ K;

    cout<< K;

}

}

若输入的a数组是一个严格单调递增的数列,分析此程序的时间复杂度。

  • 写回答

1条回答 默认 最新

  • _GX_ 2022-03-05 12:37
    关注

    第一个for循环是O(N)
    由于a数组是严格单调递增,第二个循环里的if条件不成立,故每次i循环时K不会被重置,while循环当i=1时,条件不成立,当i>=2时,++K只执行一次,因此第二个for循环的时间复杂度也是O(N)
    最终整个函数的时间复杂度时O(N)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 6月21日
  • 已采纳回答 6月13日
  • 创建了问题 3月5日

悬赏问题

  • ¥15 Abaqus打不开cae文件怎么办?
  • ¥20 双系统开机引导中windows系统消失问题?
  • ¥15 小程序准备上线,软件开发公司需要提供哪些资料给甲方
  • ¥15 关于生产日期批次退货退款,库存回退的问题
  • ¥15 手机应用的时间可以修改吗
  • ¥15 docker 运行OPEN-webui异常
  • ¥15 麒麟系统如何删除光盘刻录痕迹
  • ¥15 recipe通过gem协议传的是什么
  • ¥15 TS2307: Cannot find module 'cc'.
  • ¥15 100小时学会sap 书上pp章节5.22,标准成本计算逻辑?