1. 算法復(fù)雜度

??算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和內(nèi)存資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度主要衡量一個算法的運行快慢，而空間復(fù)雜度主要衡量一個算法運行所需要的額外空間。

??在計算機發(fā)展的早期，計算機的存儲容量很小，所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度，所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù)雜度。

1.1 時間復(fù)雜度

??時間復(fù)雜度的定義：在計算機科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復(fù)雜度這個分析方式。

??一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜度。分析算法復(fù)雜度步驟如下：

1. 找出算法的基本運算，即主要的操作。
2. 估算出執(zhí)行次數(shù)，這通常與算法思想、問題規(guī)模和特定輸入有關(guān)。

即找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達式，就是算出了該算法的時間復(fù)雜度。

1.2 大O漸進表示法

??大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學(xué)符號，用它可以表達一個算法運行時間的最小上界。

1.2.1 例子引入推導(dǎo)大O法

例：下面fun函數(shù)的時間復(fù)雜度，用大O法如何表示呢？

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--){++count;}
}

??首先我們得找到基本運算：即自增操作，而這三個自增操作執(zhí)行次數(shù)，如果要精確地算的話：f(n) = n² + 2 * n + 10。

??實際中我們計算時間復(fù)雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。先說結(jié)論，fun函數(shù)的復(fù)雜度用大O法表示為：O(n²)。

推導(dǎo)大O階方法：

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

為什么要這樣呢？我們可以對fun函數(shù)往大的問題規(guī)模去對比：

• n = 10：F(N) = 100 + 20 + 10；
• n = 100：F(N) = 10000 + 200 + 10；
• n = 1000：F(N) = 1000000 + 2000 + 10；
• n = 10000：F(N) = 100000000 + 20000 + 10；

可以發(fā)現(xiàn)n越大，直至當(dāng)n趨于無窮，剩下的 2 * n + 10的次數(shù)已經(jīng)不重要了，去掉了這幾項，也不對結(jié)果造成影響。

另外有些算法的時間復(fù)雜度存在最好、平均和最壞情況：

1. 最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
2. 平均情況：任意輸入規(guī)模的期望運行次數(shù)
3. 最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)

例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x

1. 最好情況：1次找到
2. 最壞情況：N次找到
3. 平均情況：N/2次找到

在實際中一般情況關(guān)注的是算法的最壞運行情況，說一個算法的時間復(fù)雜度默認(rèn)指的是最壞情況，即這個算法我們不能保證它一直都是最好情況，所以數(shù)組中搜索數(shù)據(jù)時間復(fù)雜度為O(N)。

1.2.2 舉例

// 復(fù)雜度為O(n)，其中M并不會隨著輸入而影響復(fù)雜度。
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

// 復(fù)雜度為O(N+M)
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;}printf("%d\n", count);
}

這個復(fù)雜度也可以這么說，當(dāng)N遠大于M時，復(fù)雜度為O(N)，反過來就是O(M)。

// 常數(shù)詞，O(1)
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}

// 最壞O(n)，不明白的話得你弄清楚strchr的功能（從一個字符串查找某個字符）
const char * strchr ( const char * str, int character );

// 最壞執(zhí)行了(N*(N+1)/2次，O(n^2)
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

// 最壞O(logn)
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n-1;// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號while (begin <= end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end = mid-1;elsereturn mid;}return -1;
}

// 遞歸了N次，O(n)
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;

// O(2^n)，可以畫遞歸樹自己理解，或者用遞歸方程求解
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

常見的復(fù)雜度如下：

1. 常數(shù)階：O(1)；
2. 線性階：O(n)；
3. 平方階：O(n²)；
4. 對數(shù)階：O(logn)；
5. 線性對數(shù)階：O(nlongn)；
6. 立方階：O(n³)；
7. 指數(shù)階：O(2ⁿ)。

注意對數(shù)階是以2為底的（log₂n），通常省略底數(shù)2。前六個復(fù)雜度屬于多項式時間算法的漸進復(fù)雜度；第七個屬于指數(shù)時間算法的漸進復(fù)雜度，其中還有階乘階O(n!)和O(nⁿ)，指數(shù)階已經(jīng)很離譜了，后面這兩種就更離譜了，所以不常見。

1.3 空間復(fù)雜度

??空間復(fù)雜度也是一個數(shù)學(xué)表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。空間復(fù)雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)。空間復(fù)雜度計算規(guī)則基本跟實踐復(fù)雜度類似，也使用大O漸進表示法。

1.3.1 細分

程序運行所需的存儲空間包括兩部分：

1. 固定空間需求：包括程序代碼、常量、變量等；

2. 可變空間需求：與程序處理的數(shù)據(jù)規(guī)模有關(guān)，如1000大小的數(shù)組和10大小數(shù)組顯然是不同的；以及與算法執(zhí)行所需的額外空間，比如遞歸算法會需要?？臻g，不過要注意的是棧幀空間是可以復(fù)用的，一旦上次函數(shù)遞歸調(diào)用結(jié)束，棧內(nèi)存空間就還給操作系統(tǒng)了，下次遞歸調(diào)用再申請使用這塊空間。

??注意：函數(shù)運行時所需要的棧空間(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。如果要減少空間復(fù)雜度，只能從可變空間這塊下手。

1.3.2 舉例

// 開辟了常數(shù)個額外空間，因此空間復(fù)雜度為O(1)。
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

只要這個程序的空間復(fù)雜度不會隨著輸入規(guī)模的增大而增大，那么空間復(fù)雜度就是常數(shù)階。

// 動態(tài)開辟了N個空間，空間復(fù)雜度為 O(N)。
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;
}

// 遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間，空間復(fù)雜度為O(N)。
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

2.什么是好的算法？

一個好的算法應(yīng)該具有以下特點：

1. 正確性。

??算法的執(zhí)行結(jié)果應(yīng)當(dāng)是解決某個問題的，否則不叫算法，最多稱之為程序或是程序的正確性。程序健壯性與算法正確性有直接關(guān)系，算法最終會被編寫為程序，而程序健壯性與算法正確性互補，算法應(yīng)當(dāng)被正確地編寫為健壯的程序。

??對于大型系統(tǒng)，指望算法“完全正確”是不可能的，不過對于程序而言也許做不到完全正確，但卻可以要求程序是健壯的。當(dāng)存在不合法的操作時，程序能做出處理而不會引起嚴(yán)重后果。

?? 正確的程序不一定是健壯的，而健壯的程序不一定完全正確。一個程序應(yīng)當(dāng)能在正常的情況下運行，也應(yīng)當(dāng)能在“異?！鼻闆r下運行并做出處理，這是程序的可靠性。

2. 簡明性。

??算法思想的邏輯清晰，易于閱讀和理解，易于編碼和調(diào)試。這個特性或許有些主觀，但簡明性并不是可有可無的特性，這是算法設(shè)計者應(yīng)當(dāng)爭取的，更容易理解的算法在編寫為程序后，也往往能減少更多的錯誤。不過遺憾的是簡明的算法，不一定高效，這與算法的高效性有矛盾，但不沖突，可以結(jié)合兩者做到算法的最優(yōu)。

3. 高效性。

??指的是執(zhí)行一個算法所需花費的時間是高效率的，且有效地使用內(nèi)存。當(dāng)程序規(guī)模較大時，設(shè)計算法經(jīng)常會為了高的時間效率而占用更多的內(nèi)存空間效率，雖說隨著計算機硬件高速發(fā)展，現(xiàn)已太不關(guān)注內(nèi)存的占用情況。但是如果為了高效的時間，卻會導(dǎo)致算法的可讀性變差，這并不是明智的選擇。因此算法設(shè)計者應(yīng)當(dāng)考慮到算法的簡明性和高效性，做出折中辦法。

4. 最優(yōu)性。

??算法執(zhí)行時間已經(jīng)達到求解該問題所需時間的下界，即沒有比它更快的算法了，最多持平。算法最優(yōu)性與求解的問題復(fù)雜度有關(guān)，如果一個算法在一個問題的最壞情況下任然能得到正確的結(jié)果，那么可以認(rèn)為這個算法是最優(yōu)的。

3. 影響程序運行時間的因數(shù)

算法會被編寫為程序，所以程序運行時間與算法時間復(fù)雜度有著密切關(guān)系。

1. 算法的好壞。

如果排除計算機系統(tǒng)和硬件情況，這是根本和決定性因數(shù)。

2. 問題的規(guī)模。

一般指輸入的數(shù)據(jù)量，比如對1000個數(shù)排序和1000000個數(shù)排序。

3. 特定的輸入數(shù)據(jù)。

例如從一個順序表中查詢指定輸入的值，這個值在順序表中的位置很關(guān)鍵。如果剛好在第一個，那么很快就能查到；如果是最后一個的話，那就是最壞情況了。

4. 計算機系統(tǒng)和硬件。

對于影響程序運行是很好理解的，但這個情況針對算法而言是不考慮的，算法只考慮算法自身能不能做到最優(yōu)，而不是去要求更好的硬件。