同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
推导大O阶
推导攻略:
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数
常数阶
常数阶用O(1)表示
线性阶
线性阶用O(n)表示
示例:如下代码的时间复杂度即为O(n)
int I ,n = 100, sum = 0;
for(I = 0 ; I < n; I++){
sum = sum + I;
}
平方阶
平方阶用O(n²)表示
示例:如下代码的时间复杂度即为O(n²)
int I , j , n = 100;
for (I = 0; I < n; I++){
for(j = 0; j < n; j ++ ){
printf("666")
}
}
对数阶
对数阶用O(logn)表示
示例:如下代码的时间复杂度即为O(logn)
int I = 1, n = 100;
while(I < n){
I = I * 2
}
//由于2^x = n ,所以x = log(2)n
常见时间复杂度
| 时间复杂度 | 术语 | 例子 |
|---|---|---|
| O(1) | 常数阶 | 123 |
| O(n) | 线性阶 | 2n+3 |
| O(n²) | 平方 | 3n²+4n+5 |
| O(logn) | 对数阶 | 3log(2)n + 5 |
| O(nlogn) | nlogn阶 | 2n + 3nlog(2)n + 10 |
| O(n³) | 立方阶 | n³+3n²+4n+5 |
| O(2^n) | 指数阶 | 2^n |
常见时间复杂度耗费时间从小到大依次是: O(1)<O(logn)<(O(n))<O(nlogn)<O(n²)<O(n³)<O(2^n)
空间复杂度
与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:
S(n)=O(f(n))
