总有一天你的谜底会解开 2021-04-23 14:52 采纳率: 77.4%
浏览 77
已采纳

C语言语句频度和时间复杂度的新手问题。

书上说 T(n)= O(f(n))中的f(n)一般为算法中频度语句最大的语句频度。

但是接下来书又举了一个例子:

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

x++;

书上说这个例子的时间复杂度 是O(n).

我的理解:程序第一行for的语句频度为 n+1,第二行x++的语句频度为n,时间复杂度为何不是O(n+1) 

  • 写回答

2条回答 默认 最新

  • obitosbb 2021-04-23 15:03
    关注

    你这个错在,执行语句的计算,不是看for里的语句,而是看x++这个执行次数;

    其次,n+1约等于n,即使是O(n+1),时间复杂度也是O(n),1可以省略;

    给你举个例子,已经排序好的数组,如果再用冒泡排序,时间复杂度也是0

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题