目錄

一、算法

1.基本概念

2.描述方法

3.算法效率

二、算法的時間復雜度

三、算法的空間復雜度

---

一、算法

1.基本概念

通俗的講，算法是解決問題的方法，比如在現實生活中一道菜譜，一個安裝輪椅的操作指南等。

嚴格的說，算法是對特定問題求解步驟的一種描述，是指令的有限序列。

算法具有的基本特性有：

（1）有窮性。一個算法必須總是在執行有窮步之后結束，且每一步都在有求時間內完成。

（2）確定性。算法中的每一條指令必須有確切的含義，不存在二意性。

（3）可行性。這個算法是可執行的。并且算法的每一條指令都可以被分解為基本的可執行的操作步驟。

一個“好”算法還具有正確性，健壯性，可理解性，抽象分級，高效性等特性。

2.描述方法

算法的描述方法可以將所設計算法中設計的求解步驟記錄下來。常用的描述算法的方法有自然語言、流程圖、程序設計語言和偽代碼等。

3.算法效率

如何衡量一個算法的效率？

????????每當算法在編寫成可執行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。

時間復雜度 主要衡量一個算法的運行快慢。

空間復雜度 主要衡量一個算法運行所需要的額外空間。

二、算法的時間復雜度

????????撇開與計算機應硬軟件有關的因素，影響算法時間代價的最主要因素是問題規模。所以運行算法所需要的時間T就是問題規模n的函數，記作 T(n)。它定量描述了該算法的運行時間。

????????一 個算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。

????????為了客觀的反映一個算法的執行時間。可以用算法中基本語句的執行次數來度量算法的工作量（基本語句是執行次數與整個算法執行次數成正比的語句）。

????????只考察當問題規模充分大時。算法中基本語句的執行次數在漸進意義下的階稱作算法的漸進時間復雜度。簡稱為時間復雜度。

????????簡而言之，一個算法所花費的時間與其中基本語句的執行次數成正比例，算法中的基本操作語句的執行次數，為算法的時間復雜度。到某條基本語句與問題規模n之間的數學表達式，就算出了該算法的時間復雜度。

????????但是，有時我們在計算基本語句的執行次數時，可能會發現有些次數計算時非常麻煩。所以實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么就需要使用大O的漸進表示法。

大O的漸進表示法：

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

推導大O階方法： ?

1、用常數1取代運行時間中的所有加法常數。

2、在修改后的運行次數函數中，只保留最高階項。

3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。

舉例：計算時間復雜度

void Func(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

這里的問題規模是N，基本語句為++count，基本操作次數為F(N)=2N+10，那么有大O的漸進表示法就為O(n)。

常見的時間復雜度有：

三、算法的空間復雜度

????????空間復雜度也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。

????????空間復雜度不是算程序占用了多少字節的空間，而算的是變量的個數。 空間復雜度計算規則基本跟實踐復雜度類似，也使用大O的漸進表示法。

算法在運行過程中所需的存儲空間包括：

①輸入輸出數據占用的空間;②算法本身占用的空間；③執行算法需要的輔助空間。

其中，輸人輸出數據占用的空間取決于問題，與算法無關；算法本身占用的空間雖然與算法相關，但一般其大小是固定的。所以，算法的空間復雜度是指算法在執行過程中需要的輔助空間數量，也就是除算法本身和輸人輸出數據所占用的空間外,算法臨時開辟的存儲空間。

????????函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候申請的額外空間來確定。

舉例1：計算空間復雜度

void Bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){int flag = 0;int j = 0;for (j = 0; j < sz - 1 - i; j++){//從小到大排序if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = 1;}}if (flag == 0){break;}}
}

這段代碼中所有變量均為預先確定數量的局部變量： ?int i、int flag、int j、int temp（總計4個整型變量）所以空間復雜度是O(1)。

舉例2：計算空間復雜度

long long* Fibonacci(size_t n)
{if (n == 0){return NULL;}long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));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)