Java數據結構–時間和空間復雜度

Posted on by

一、算法效率

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

時間效率

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

空間效率

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

二、時間復雜度 

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)

四、總結

本片文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：