數據結構知識點合集：數據結構與算法
? 知識點
? 時間復雜度的定義
1、算法時間復雜度
??事前預估算法時間開銷T(n)與問題規模 n 的關系（T 表示 “time”）
2、語句頻度
??算法中語句的執行次數
??對于以上算法，語句頻度：
????① ——1次 ② ——3001次 ③④ ——3000次 ⑤ ——1次
????T(3000) = 1 + 3001 + 2*3000 + 1
??時間開銷與問題規模 n 的關系：
????T(n)=3n+3
??大O記號表示算法的一種漸近時間復雜度；大O表示“同階”，同等數量級。即：當 n->∞時，二者之比為常數
??結論1：可以只考慮階數高的部分
??結論2：問題規模足夠大時，常數項系數也可以忽略
? 時間復雜度的計算規則
1、加法規則
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
??多項相加，只保留最高階的項，且系數變為1
2、乘法規則
T(n) = T1(n)×T2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
??多項相乘，都保留
3、常見時間復雜度的比較
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
??常<對<冪<指<階
4、順序執行的代碼只會影響常數項，可以忽略
5、只需挑循環中的一個基本操作分析它的執行次數與 n 的關系即可
6、如果有多層嵌套循環，只需關注最深層循環循環了幾次
例：計算以下算法的時間復雜度 T(n)：
??設最深層循環的語句頻度（總共循環的次數）為 x，則由循環條件可知，循環結束時剛好滿足 2^x > n
??x = log_2(n) + 1
??T(n) = O(x) = O(log_(2)n)
? 三種常用的時間復雜度
最壞時間復雜度：最壞情況下算法的時間復雜度
平均時間復雜度：所有輸入示例等概率出現的情況下，算法的期望運行時間
最好時間復雜度：最好情況下算法的時間復雜度
