:star:前面的話:star:

本篇文章帶大家認識資料結構與算法基礎，時間複雜度與空間複雜度。算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度，而空間效率被稱作空間複雜度。時間複雜度主要衡量的是一個算法的運作速度，而空間複雜度主要衡量個算法所需要的額外空間，在計算機發展的早期，計算機的存儲容量很小。是以對空間複雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。是以我們如今已經不需要再特别關注一個算法的空間複雜度。描述代碼：Java。

:ledger:部落格首頁：未見花聞的部落格首頁

:tada:歡迎關注:mag_right:點贊:+1:收藏:star:留言:memo:

:pushpin:本文由未見花聞原創！

:calendar:51CTO首發時間：:palm_tree:2021年12月17日:palm_tree:

:envelope:堅持和努力一定能換來詩與遠方！

:thought_balloon:參考書籍：:books:《趣學資料結構》，:books:《資料結構(C語言版)》，:books:《趣學算法》

:speech_balloon:參考線上程式設計網站：:globe_with_meridians:牛客網:globe_with_meridians:力扣

:pray:作者水準很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！

部落客的碼雲gitee，平常部落客寫的程式代碼都在裡面。

部落客的github，平常部落客寫的程式代碼都在裡面。

(📌導航小助手📌)

🍓1.問題導入

🍇1.1引入複雜度

🍊求下面序列之和∶

$$-1,1,-1,1,...,(-1)^n$$

第一種做法：

public static int sumAdd(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += (int)Math.pow(-1, i);
        }
        return sum;
    }

該程式執行了n次。

第二種做法：

public static int sumAddPlus(int n) {
        int sum = 0;

        if (n % 2 == 1) {
            sum = -1;
        }

        return sum;
    }

該程式執行了1次。

可見不同的算法，可能會有着不同的執行次數，執行的次數越少，則程式所費時間越少，說明算法越優。

是以我們使用程式的執行次數作為判斷一個程式運作速度快慢的标準，這個執行次數就稱為一種算法的時間複雜度。

🍇1.2棋盤麥子問題

我來帶大家認識一種恐怖的爆炸增量，相信大家都聽說過棋盤麥子的故事：

有一個古老的傳說，有一位國王的女兒不幸落水，水中有很多鳄魚，國王情急之下下令∶"誰能把公主救上來，就把女兒嫁給他。"很多人紛紛退讓，一個勇敢的小夥子挺身而出，冒着生命危險把公主救了上來，國王一看是個窮小子，想要反悔，說∶"除了女兒，你要什麼都可以。"小夥子說∶"好吧，我隻要一棋盤的麥子。您在第1個格子裡放1粒麥子，在第2 個格子裡放2粒，在第3個格子裡放4粒，在第4個格子裡放8粒，以此類推，每一格子裡的麥子粒數都是前一格的兩倍。把這64個格子都放好了就行，我就要這麼多。"國王聽後哈哈大笑，覺得小夥子的要求很容易滿足，滿口答應。結果發現，把全國的麥子都拿來，也填不完這64格……國王無奈，隻好把女兒嫁給了這個小夥子。

棋盤上的64個格子究竟要放多少粒麥子?把每一個放的麥子數加起來，總和為S，則∶

$$S=1+2^1+2^2+2^3+...+2^{63}$$

等式兩邊同乘以2，得：

$$2S=2^1+2^2+2^3+2^4+...+2^{64}$$

兩式做差，得：

$$S=2^{64}-1 = 18446744073709 551615$$

據專家統計，每個麥粒的平均重量約41.9毫克，那麼這些麥粒的總重量是∶

$$18446744073709551615×41.9=772918576688430212668.5（毫克）≈7729（億噸）$$

全世界人口按60億計算，每人可以分得128噸!

我們稱這樣的函數為爆炸增量函數，想一想，如果算法時間複雜度是$O(2^n)$會怎樣?随着n的增長，這個算法會不會"爆掉"?經常見到有些算法調試沒問題，運作一段也沒問題，但關鍵的時候當機（shutdown）。例如，線上考試系統，50 個人考試沒問題，100 人考試也沒問題，如果全校1萬人考試就可能出現當機。

注意∶當機就是當機，指電腦不能正常工作了，包括一切原因導緻的當機。計算機主機出現意外故障而當機，一些伺服器（如資料庫）死鎖，伺服器的某些服務停止運作都可以稱為當機。

常見的算法時間複雜度有以下幾類：

常數階，如$O(1)$。
多項式階，如$O(n^2),O(n^3),O(n^4)$等。
指數階，如棋盤麥子，遞歸實作斐波拉契數列$O(2^n)$。
對數階，如二分查找$O(log_2n)$。

根據對應函數的趨勢圖：

$$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

一般我們設計算法時，時間複雜度最好小于$O(n^2)$。

🍓2.時間複雜度

🍇2.1概念

時間複雜度的定義：在計算機科學中，算法的時間複雜度是一個函數，它定量描述了該算法的運作時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，隻有你把你的程式放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，是以才有了時間複雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間複雜度。

🍇2.2時間複雜度的計算

// 請計算一下func1基本操作執行了多少次？
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 < 2 * N ; k++) {
       count++;
   }
   int M = 10;
   while ((M--) > 0) {
       count++;
   }
   System.out.println(count);
}

對于這個程式，首先兩層嵌套的for循環每層都執行了

次，是以它執行的次數為

n*n

，即n^2^。然後執行單層的for循環，執行次數為

2n

，最後執行了單層的while循環，執行次數為

m = 10

。是以該程式一共執行的次數為$T(n)$：

$$T(n) = n^2 +2n + 10 $$

$n = 10, T(n) = 130$

$n = 100, T(n) = 10210$

$n = 1000, T(n) = 1002010$

...

當$n$趨近于無窮大時，我們發現除最高階外其他的低階項或常數項可以忽略。

我們實際要計算時間複雜度時，隻計算它的大概的執行次數，是以對于複雜度我們取對程式執行次數起主要因素的一項，也就是最高階項，并且最高階的系數一律置為

，因為當$n$趨近于無窮大時多乘一個系數少乘一個系數都對複雜度沒有很大的影響。這種方法也稱“大O的漸進表示法”。

大O符号（Big O notation）：是用于描述函數漸進行為的數學符号。

推導大O階方法：

用常數1取代運作時間中的所有加法常數。
在修改後的運作次數函數中，隻保留最高階項。
如果最高階項存在且不是1，則去除與這個最高階項相乘的常數，得到的結果就是大O階。

另外，算法的時間複雜度存在最好，平均，最差情況。我們所計算的時間複雜度一般為最壞情況下的複雜度，因為計算最好情況與平均情況的複雜度意義不大，最壞情況下的時間複雜度才能展現一個程式的性能好壞。

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

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

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

是以該程式的時間複雜度為$O(n^2)$

下面我們就開始來小試牛刀一下：

🍊題1

// 計算func2的時間複雜度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
   count++; 
}
int M = 10;
while ((M--) > 0) {
   count++; 
}
System.out.println(count);
}

該程式執行次數為$T(n)$：

$$T(n) = 2n + 10$$

時間複雜度為$O(n)$

🍊題2

// 計算func3的時間複雜度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
   count++; 
}
for (int k = 0; k < N ; k++) {
   count++; 
}
System.out.println(count);
}

該程式執行次數為$T(n,m)$：

$$T(n,m) = m + n$$

時間複雜度為$O(m + n)$

🍊題3

// 計算func4的時間複雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
   count++; 
}
System.out.println(count);
}

該程式執行次數為$T(n)$：

$$T(n) = 100$$

$T(n)$為一個常數，是以時間複雜度為$O(1)$

🍊題4

// 計算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;
       }
   }
}

該程式最壞情況下執行次數為$T(n)$：

$$T(n) = n - 1 + n - 2 + ... + 1 +0 =n*(n-1)/2$$

時間複雜度為$O(n^2)$

🍊題5

// 計算binarySearch的時間複雜度？
int binarySearch(int[] array, int value) {
   int begin = 0;
   int end = array.length - 1;
   while (begin <= end) {
       int mid = begin + ((end-begin) / 2);
       if (array[mid] < value)
           begin = mid + 1;
       else if (array[mid] > value)
           end = mid - 1;
       else
           return mid;
   }
   return -1; 
}

這是一個二分查找的程式，每循環一次，排除的元素就少一半，我們設該程式的執行次數為$T(n)$，元素個數為$n$，當查找剩餘元素個數為1個時，程式還需要查找一次，是以當執行$T(n)-1$次時，剩餘的元素個數為1，則有下面等式：

$$n/2^{(T(n)-1)} = 1$$

即：$$ 2^{(T(n)-1)} = n$$

該程式執行次數為$T(n)$：

$$T(n) = log_2 n + 1$$

時間複雜度為$O(log_2n)\ 或\ O(logn)$

🍊題6

// 計算階乘遞歸factorial的時間複雜度？
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N; 
}

該程式需要遞歸的次數為$n$次，是以它的時間複雜度為$O(n)$

🍊題7

// 計算斐波那契遞歸fibonacci的時間複雜度？
int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

不考慮右邊最後缺失的幾次遞歸，大概的遞歸次數為$T(n)$

$$T(n)=1 + 2^1 + 2^2 + ...+ 2^{(n-1)}$$

由等比數列求和公式：

$$T(n) = 2^n - 1$$

是以斐波拉契數列遞歸實作的時間複雜度為$O(2^n)$，在前面的麥子棋盤已經可知該時間複雜度的恐怖性。

🍓3.空間複雜度

🍇2.1概念

空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的量度。空間複雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，是以空間複雜度算的是變量的個數。空間複雜度計算規則基本跟時間複雜度類似，也使用大O漸進表示法。

🍇2.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+1$的長整型數組記憶體空間，空間複雜度為$O(n)$。

// 計算階乘遞歸Factorial的空間複雜度？
long factorial(int N) {
 	return N < 2 ? N : factorial(N-1)*N; 
}

遞歸求階乘一共遞歸了$n$次，每次開辟的記憶體是常數級的，使用空間複雜度為$O(n)$。

留給讀者：遞歸實作斐波拉契數列空間複雜度為多少？

答案是$O(2^n)$，知道為什麼嗎？思考一下吧！

#yyds幹貨盤點# 資料結構與算法之時間複雜度與空間複雜度🍓1.問題導入🍓2.時間複雜度🍓3.空間複雜度

🍓1.問題導入

🍇1.1引入複雜度

🍇1.2棋盤麥子問題

🍓2.時間複雜度

🍇2.1概念

🍇2.2時間複雜度的計算

🍓3.空間複雜度

🍇2.1概念

🍇2.2空間複雜度的計算

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器