如何评判一个算法的好坏？
- 正确性、可读性、健壮性（对不合理输入的反应能力）
- 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
- 空间复杂度（space complexity）：估算所占用的存储空间
大O表示法（估算复杂度）
一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
忽略常数、系数、低阶
- 9 >> O(1)
- 2n+3 >> O(n)
- n^2+2n+6 >> O(n^2)
- 4n^3 +3n^2+22n+1 >> O(n^3)
对数阶的细节
log2(n) = log2(9) * log9(n)
所以：log2(n)、log9(n)统称为log(n)（无论底数多少都一样）
复杂度排序
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
举例算法复杂度
//时间复杂度O(1)
for (int i = 0; i < 30; i ++) {
NSLog(@"你好老弟");
}
//时间复杂度O(n)
for (int i = 0; i < n; i ++) {
NSLog(@"你好老弟");
}
//时间复杂度O(n^2)
for (int i = 0; i < n; i ++) {
for (int j = 0; j<n; j++) {
NSLog(@"你好老弟");
}
}
//时间复杂度O(logn)
while ((n = n / 2) > 0) {
NSLog(@"你好老弟");
}
//时间复杂度O(logn)
while ((n = n / 5) > 0) {
NSLog(@"你好老弟");
}
//时间复杂度O(logn)
for (int i = 0; i < n; i += i) {
NSLog(@"你好老弟");
}
算法优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤
- 根据情况，可以用空间换时间，或用时间换空间
总结：算法复杂度的差距决定程序的性能
