在长大
2021-04-23 14:52
采纳率: 93.6%
浏览 49

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条)

相关推荐 更多相似问题