一、算法效率
算法效率分析分為兩種：時間效率和空間效率

時間效率

時間效率被稱為時間復雜度，主要時衡量一個算法的運行速度。

空間效率

空間效率被稱為空間復雜度，主要衡量一個算法所需要的額外空間。

二、時間復雜度

1. 概念

一個算法所花費的時間與其中語句的執行次數成正比，故將算法中的基本操作的執行次數，作為算法的時間復雜度。

并且時間復雜度其實還可以分成三種情況：

最壞情況：任意輸入規模的最大運行次數
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數

而在實際中一般關注的是算法的最壞運行情況。

2. 大 O 的漸進表示法

實際在我們計算時間復雜度時，并不一定要計算精確的執行次數，而只需要大概執行次數，故我們使用大 O 的漸進表示法（大 O 符號是用于描述函數漸進行為的數學符號）。

使用方法

用常數1取代運行時間中的所有加法常數。
在修改后的運行次數函數中，只保留最高階項。
如果最高階項存在且不為1，則去除與這個項目相乘的常數。
如某個算法的基本操作次數為 F(N) = N^2^ + 2*N + 10，用大 O 的漸進表示法為：O(N)。

3. 練習

在這里放入兩個遞歸函數的練習，我們來試著推導其的時間復雜度。

練習一：計算階乘遞歸 factorial 的時間復雜度

long factorial(int N) {return N < 2 ? N : factorial(N-1) * N; }

這題很簡單，結果為：O(N)。

練習二：計算斐波那契遞歸 fibonacci 的時間復雜度

int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2); }

這題可以結合畫圖類似于二叉樹去思考，結果為：O(N2)

注意

遞歸的時間復雜度 = 遞歸的次數 * 每次遞歸內容要執行的次數

三、空間復雜度

1. 概念

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度，它不是計算程序占用了多少 byte 的空間，而是計算變量的個數。（空間復雜度也使用大 O 的漸進表示法）。

2. 練習

練習一：計算 bubbleSort 的空間復雜度

void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}} }

因為只使用了常數個額外空間，故結果為：O(1)。

練習二：計算 fibonacci 的空間復雜度

int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray; }

因為動態開辟了 N 個空間，故結果為：O(N)。

練習三：計算階乘遞歸 Factorial 的時間復雜度

long factorial(int N) {return N < 2 ? N : factorial(N-1)*N;? }

因為遞歸調用了 N 次，開辟了 N 個棧幀，每個棧幀使用了常數個空間，故結果為：O(N)。

希望能對大家有所幫助，歡迎三連。

總結

以上是生活随笔為你收集整理的时间和空间复杂度概述【Java _demo版】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。