1.算法效率

算法效率分析分為兩種 : ①時間效率, ②空間效率?

時間效率即為 時間復雜度 , 時間復雜度主要衡量一個算法的運行速度

空間效率即為 空間復雜度 , 空間復雜度主要衡量一個算法所需要的額外空間

2.時間復雜度

2.1 時間復雜度的概念

定義 : 再計算機科學中 , 算法的時間復雜度 是一個數學函數 , 它定量描述了 該算法的運行時間

用于衡量算法執行時間 隨輸入規模增長的變化趨勢

2.2 大O的漸進表示法

計算func基本操作執行了多少次?

    public static void func1(int N){int count = 0;for(int i = 0;i<N;i++){for(int j = 0;j<N;j++){count++;}}for(int k = 0;k<N*2;k++){count++;}int m = 10;while((m--)>0){count++;}System.out.println(count);}

func1執行基本操作次數:

F(N) = N^2 + 2*N + 10?

實際中我們計算時間復雜度時 , 我們其實不一定要計算精確的執行次數 , 而只需要大概執行次數 , 那么我們這里使用大O的漸進表示法

O :?用于描述函數漸進行為的數學符號

2.3 推導大O階方法

• 用常數 1 取代運行時間中的所有加法常數
• 再修改后的函數中 , 只保留最高階項
• 如果最高階存在且不是1, 則取出這一項的系數 , 結果就是大O階

例如: func1使用大O簡靜法表示后 , func1的時間復雜度為 O(N^2)

通過用大O的漸進表示法 去掉了對結果影響不大的項 , 簡潔明了的表示出了執行次數

另外 有些算法還存在 時間復雜度 最好 , 最壞 , 平均的情況

最壞情況 : 任意輸入規模的最大運行次數 (上界)

平均情況 : 任意輸入規模的期望運行次數

最好情況 : 任意輸入規模的最小運行次數 (下界)

例如: 一個長度為N的數組中尋找一個數據 X

最好情況 : 一次找到? ? 最壞情況 : N次找到? ?平均情況 : N/2次找到

在實際中一般關注的是算法的 最壞運行情況 , 所以數組中搜索數據的時間復雜度為O(N)

3.空間復雜度

定義 : 是對一個算法在運行過程中臨時占用空間大小的度量

用于評估算法對內存資源的消耗情況

空間復雜度計算的是 變量的個數

O(1) 常數空間

int sum(int a, int b) {int result = a + b; // 僅占用固定空間return result;
}