书上说 T(n)= O(f(n))中的f(n)一般为算法中频度语句最大的语句频度。
但是接下来书又举了一个例子:
for(i=1;i<=n;i++)
x++;
书上说这个例子的时间复杂度 是O(n).
我的理解:程序第一行for的语句频度为 n+1,第二行x++的语句频度为n,时间复杂度为何不是O(n+1)
书上说 T(n)= O(f(n))中的f(n)一般为算法中频度语句最大的语句频度。
但是接下来书又举了一个例子:
for(i=1;i<=n;i++)
x++;
书上说这个例子的时间复杂度 是O(n).
我的理解:程序第一行for的语句频度为 n+1,第二行x++的语句频度为n,时间复杂度为何不是O(n+1)
你这个错在,执行语句的计算,不是看for里的语句,而是看x++这个执行次数;
其次,n+1约等于n,即使是O(n+1),时间复杂度也是O(n),1可以省略;
给你举个例子,已经排序好的数组,如果再用冒泡排序,时间复杂度也是0