一、算法效率

算法效率分析分為兩種：時(shí)間效率和空間效率

時(shí)間效率

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

空間效率

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

二、時(shí)間復(fù)雜度 

1. 概念

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

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

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

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

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

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

使用方法

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

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

3. 練習(xí)

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

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

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

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

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

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

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

注意

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

三、空間復(fù)雜度 

1. 概念

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

2. 練習(xí)

練習(xí)一：計(jì)算 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;
         }
    }
}

因?yàn)橹皇褂昧顺?shù)個(gè)額外空間，故結(jié)果為：O(1)

練習(xí)二：計(jì)算 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;
}

因?yàn)閯?dòng)態(tài)開辟了 N 個(gè)空間，故結(jié)果為：O(N)

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

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

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

四、總結(jié)

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

最新評(píng)論