前言

小伙伴們大家好，好久未寫博文了，這樣不好，今天博主要繼續更新了，最近博主在學習資料結構，希望可以持續地將學習成果分享給大家，請大家多多支持哦！！！那么今天呢我們就來寫一寫關于復雜度的講解，

一、復雜度是個what？

在這里插入圖片描述

首先，我們先來了解幾個概念：

1.演算法效率：

演算法效率分析分為兩種：
第一種是時間效率，第二種是空間效率，
時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，而更關注一個演算法的時間復雜度

2.時間復雜度

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

二、大O的漸進表示法

1.為什么要用漸進表示法？

因為復雜度是有“大格局的優雅者”，而“斤斤計較”并不優雅，我們沒有必要把所有細枝末節都算上，那樣結果冗余復雜且沒有什么價值，我們只要選取對結果影響最大的部分就好，
我們來看一個例子：

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;
}
printf("%d\n", count)

我們來分析一下：

Func1 執行的基本操作次數：
在這里插入圖片描述

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

我們觀察到，在上面的例子中，N*N的階數最高，對結果的影響最大，而其余對結果的影響微乎其微甚至可以忽略不計，實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這
里我們使用大O的漸進表示法，
大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，

2.推導大O階方法：

1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，

使用大O的漸進表示法以后，Func1的時間復雜度為：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，

另外有些演算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
}
int M = 10;
while (M–)
{
++count;
}
printf("%d\n", count);
}
在實際中一般情況關注的是演算法的最壞運行情況所以陣列中搜索資料時間復雜度為O(N）

三.常見復雜度計算舉例

1.例1有系數怎么辦？

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(N)=2N+10，
那么復雜度O(N)應該是多少呢？是O(F(N))嗎?是O(2N)嗎？
在這里插入圖片描述
答案是O(N)!
讓我們來分析一下為什么是O(N)？
首先，保留最高階項2*N，然后，我們依據推導大O的方法第三條，去除系數就得到了O(N)，
那么有的小伙伴可能會問，為什么要去除系數呢？其實是這樣的，我們知道復雜度為了優雅的風度會忽略對結果影響極小的數值，那么是誰給了復雜度如此“優雅”的勇氣呢？是CPU，隨著CPU處理速度的越來越快，數十億次的運算花費時間也是極小的，所以那些階數較小的項在階數較高的項面前是完全沒有什么存在感的，也正因為如此我們可以忽略階數較小的項，忽略高階項前的系數，（就好比億萬富翁，有一億五千萬的人稱為億萬富翁，有五億的人也稱為億萬富翁，大家都是億萬富翁，）

2.例2M+N怎么辦？

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

這個O(N)又是多少呢？
通過代碼我們可知F(N)=M+N，
在這里插入圖片描述
ε=(′ο｀*)))唉，這次O(N)應該是多少呢？是O(M)?還是O(N)?還是O(M+N)呢？根據我們的三個推導大O的方法想一想應該哪一個是正確答案呢？

答案是O(M+N)，我們來分析一下，M、N的大小都是未知的，如果M比N大非常多，那么復雜度為M，因為N可以忽略，所以（M+N)近似于M，反之亦然，如果M和N的值接近，則O(N)為O(M+N)，綜上我們可以看出，復雜度為O(M+N)可以滿足所有情況，

3.例3是常數怎么辦？

void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

我們發現這個程式一共執行了100次為常數，所以復雜度為O(1)，

4.例4好幾種情況怎么辦？

const char * strchr ( const char * str, int character )；

這個怎么求呢？
在這里插入圖片描述

好像有點難啊！莫慌，我們來分析一下，
首先，我們先來了解一下strchr函式，strchr函式是對單個字符進行查找的函式，格式如下：char *strchr(const char *str, int character);
表示如果在字串str中找到字符character，回傳character在str中第一次出現的位置，如果沒找到則回傳NULL，
那么，我們可以發現，我們并不能確定character會在哪里出現，有可能會在開始出現，也有可能會在最后出現，也有可能會在中間出現，也有可能不出現，所以根據規則，我們要選取最壞的情況，也就是復雜度為O(N)，通過這個例子我們可以知道，復雜度的“優雅”不僅可以體現在它會舍棄影響微乎其微的部分，舍去同一個量級的系數，也體現在，它會照顧最壞的情況，復雜度深諳“舍得”的道理，也很“同情弱者".哈哈哈，畢竟檢驗一個演算法的文明尺度的，是它對弱者的態度，

5.例5冒泡排序怎么辦？

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

我們對于冒泡排序的思想都已經很熟悉了，那么冒泡排序的復雜度又該如何計算呢？我們來分析一下：
我們可以發現，執行最好N次，最壞執行了(N*(N+1)/2次，通過推導大O階方法+時間復雜度一般看最壞，時間復雜度為 O(N^2)
在這里插入圖片描述

6.例6二分查找怎么辦？

BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}