一、算法效率

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

時間效率

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

空間效率

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

二、時間復(fù)雜度 

1. 概念

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

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

• 最壞情況：任意輸入規(guī)模的最大運行次數(shù)
• 平均情況：任意輸入規(guī)模的期望運行次數(shù)
• 最好情況：任意輸入規(guī)模的最小運行次數(shù)

而在實際中一般關(guān)注的是算法的最壞運行情況

2. 大 O 的漸進(jìn)表示法

實際在我們計算時間復(fù)雜度時，并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，故我們使用大 O 的漸進(jìn)表示法（大 O 符號是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號）

使用方法

用常數(shù)1取代運行時間中的所有加法常數(shù)在修改后的運行次數(shù)函數(shù)中，只保留最高階項如果最高階項存在且不為1，則去除與這個項目相乘的常數(shù)

如某個算法的基本操作次數(shù)為 F(N) = N^2^ + 2*N + 10，用大 O 的漸進(jìn)表示法為：O(N)

3. 練習(xí)

在這里放入兩個遞歸函數(shù)的練習(xí)，我們來試著推導(dǎo)其的時間復(fù)雜度

練習(xí)一：計算階乘遞歸 factorial 的時間復(fù)雜度

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

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

練習(xí)二：計算斐波那契遞歸 fibonacci 的時間復(fù)雜度

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

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

注意

遞歸的時間復(fù)雜度 = 遞歸的次數(shù) * 每次遞歸內(nèi)容要執(zhí)行的次數(shù)

三、空間復(fù)雜度 

1. 概念

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

2. 練習(xí)

練習(xí)一：計算 bubbleSort 的空間復(fù)雜度

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;
         }
    }
}

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

練習(xí)二：計算 fibonacci 的空間復(fù)雜度

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;
}

因為動態(tài)開辟了 N 個空間，故結(jié)果為：O(N)

練習(xí)三：計算階乘遞歸 Factorial 的時間復(fù)雜度

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

因為遞歸調(diào)用了 N 次，開辟了 N 個棧幀，每個棧幀使用了常數(shù)個空間，故結(jié)果為：O(N)

四、總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論