復雜度是衡量代碼運行效率的重要的度量因素,一般而言,代碼執(zhí)行過程中會消耗計算時間和計算空間,這里我們需要衡量的就是時間復雜度和空間復雜度.
- 復雜度是一個關于輸入數(shù)據(jù)量n的函數(shù),O(n)表示的是復雜度與計算實例的個數(shù)n線性相關;O(logn)表示的是復雜度與計算實例的個數(shù)n對數(shù)相關.
- 復雜度與具體的常系數(shù)無關.
- 多項式級的復雜度相加的時候,選擇高者作為結(jié)果.
- O(1)表示一個特殊復雜度,表示某個任務通過有限可數(shù)的資源即可完成,與輸入數(shù)據(jù)量n無關.
經(jīng)驗結(jié)論:
1.一個順序結(jié)構的代碼,時間復雜度是O(1)
2.二分查找(二分策略),時間復雜度市O(logn)
3.一個簡單的for循環(huán),時間復雜度是O(n)
4.兩個順序執(zhí)行的for循環(huán),時間復雜度O(n) + O(n) = O(2n),其實也是O(n)
5.兩個嵌套的for循環(huán),時間復雜度是O(n2)
高效代碼要采用盡可能低的時間復雜度和空間復雜度去完成開發(fā).
1.降低時間復雜度的方法有 遞歸绍昂、二分法氮发、排序算法、動態(tài)規(guī)劃等咖摹。
2.降低空間復雜度通常需要圍繞數(shù)據(jù)結(jié)構進行研究。
降低復雜度的經(jīng)驗結(jié)論:
1寇壳、暴力破解仿荆，在沒有任何時間、空間約束下怎抛，完成代碼任務的開發(fā)。
2芽淡、無效操作處理马绝，將代碼中的無效計算、無效存儲剔除吐绵，降低時間和空間復雜度迹淌。
3、時空轉(zhuǎn)換己单，設計合理的數(shù)據(jù)結(jié)構唉窃，完成時間復雜度向空間復雜度的轉(zhuǎn)移。
