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

Question

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

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

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

x++;

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

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

Answer 1

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

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

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