如何評(píng)判一個(gè)算法的好壞点额？
- 正確性、可讀性枚荣、健壯性（對(duì)不合理輸入的反應(yīng)能力）
- 時(shí)間復(fù)雜度（time complexity）：估算程序指令的執(zhí)行次數(shù)（執(zhí)行時(shí)間）
- 空間復(fù)雜度（space complexity）：估算所占用的存儲(chǔ)空間
大O表示法（估算復(fù)雜度）
一般用大O表示法來描述復(fù)雜度，它表示的是數(shù)據(jù)規(guī)模n對(duì)應(yīng)的復(fù)雜度
忽略常數(shù)、系數(shù)芽唇、低階
- 9 >> O(1)
- 2n+3 >> O(n)
- n^2+2n+6 >> O(n^2)
- 4n^3 +3n^2+22n+1 >> O(n^3)
對(duì)數(shù)階的細(xì)節(jié)
log2(n) = log2(9) * log9(n)
所以：log2(n)、log9(n)統(tǒng)稱為log(n)（無論底數(shù)多少都一樣）
復(fù)雜度排序
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
舉例算法復(fù)雜度
//時(shí)間復(fù)雜度O(1)
for (int i = 0; i < 30; i ++) {
NSLog(@"你好老弟");
}
//時(shí)間復(fù)雜度O(n)
for (int i = 0; i < n; i ++) {
NSLog(@"你好老弟");
}
//時(shí)間復(fù)雜度O(n^2)
for (int i = 0; i < n; i ++) {
for (int j = 0; j<n; j++) {
NSLog(@"你好老弟");
}
}
//時(shí)間復(fù)雜度O(logn)
while ((n = n / 2) > 0) {
NSLog(@"你好老弟");
}
//時(shí)間復(fù)雜度O(logn)
while ((n = n / 5) > 0) {
NSLog(@"你好老弟");
}
//時(shí)間復(fù)雜度O(logn)
for (int i = 0; i < n; i += i) {
NSLog(@"你好老弟");
}
算法優(yōu)化方向
- 用盡量少的存儲(chǔ)空間
- 用盡量少的執(zhí)行步驟
- 根據(jù)情況取劫，可以用空間換時(shí)間匆笤，或用時(shí)間換空間
總結(jié)：算法復(fù)雜度的差距決定程序的性能
