- 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级
- 定义: 算法的时间复杂度，也就是算法的时间量度，记作T(n) = O(f(n))；它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,其中f(n)是问题规模n的某个函数
- 大O记法： 像定义中使用大写O来体现算法时间复杂度的方法，我们称之为大O记法。
- 推导大O阶方法:
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数 - 常数阶O(1): 与问题规模n无关、执行时间恒定的算法，我们称之为具有O(1)阶的时间复杂度，又称常数阶。
/ /不管n为多少，下面程序只执行2次 int sum = n * 2; printf('%d', sum); - 线性阶:
下面这段代码，它的循环的时间复杂度为O(n)，因为循环体中的代码须要执行n次for(int i = 0; i < n; i++){ printf("%d",i);//该语句执行n次 } - 对数阶:
int count = 1; while(count < n){ count = count * 2; }
假定x次后退出循环，则2^x = n;x=log2n;所以这个循环的时间复杂度为O(logn)
- 平方阶:
int i,j; for(i = 0; i < n; i++){ for(j = 0; j < n; j++){ //时间复杂度为O(1)的操作 } }
内循环执行n次，外循环执行n次，内循环内部是复杂度为O(1)的操作，所以时间复杂度为O(n^2);
总结：循环算法的时间复杂度等于循环的次数乘循环体的复杂度
