目錄
- 算法複雜度
-
- 大小關系對比
- 化簡方法
- 複雜度函數的基本推導過程
- 參考
算法複雜度
算法具有輸入輸出，有窮性，确定性，有限性；程式可以不滿足有限性
大小關系對比
O(c)<O(logN)<O(log^2N)<O(N)<O(N*logN) < O(N^2)<O(N^3)<O(2^N)<O(N!)<O(N^N)
在對比時，其實也可直接對N帶入具體值計算比較
化簡方法
1、用常數1取代運作時間中的所有加法常數C
2、保留最高階項
3、如果最高階項存在且不是1，去掉常數系數。比如5n^3我們取n^3，用大O表示結果
補充，有一些關于O的運算：
1、O(f+g)=O(f)+O(g)=O(max(f,g))
2、O(fg)=O(f)*O(g)
3、O(Cf(N))=O(f(N))；C是正常數
4、f = O(f)
複雜度函數的基本推導過程
需要知道的公式：
主要的方法有（主要掌握紅色的方法）：
遞歸樹的适用範圍是問題規模以等比縮減的情況.
把非函數項作為根，把函數項作為根的兒子
每層節點的值就是目前疊代的非函數項的值
遞歸樹的本質就是T(n)=樹所有節點之和
參考
課程PPT
mooc算法設計與分析