歡迎各位來到 Harper.Lee 的學習世界！

博主主頁傳送門：Harper.Lee的博客主頁

想要一起進步的uu歡迎來后臺找我哦！

????????本片博客主要介紹的是數(shù)據(jù)結構中關于算法的時間復雜度和空間復雜度的概念。

一、算法

1.1 什么是算法？

?????????算法(Algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產(chǎn)生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數(shù)據(jù)轉化成輸出結果。

1.2 算法的復雜度

????????算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
????????時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度，計算機的配置變得越來越高，對內存（空間復雜度）的關注也就沒那么高了。所以我們如今已經(jīng)不需要再特別關注一個算法的空間復雜度。目前計算機行業(yè)的硬件方面已經(jīng)遇到瓶頸期了。

摩爾定律：其核心內容是當價格不變時，集成電路上可容納的晶體管數(shù)目約每隔18個月至24個月便會增加一倍，同時性能也將提升一倍。換言之，每一美元所能買到的電腦性能，將每隔18個月翻兩倍以上。這一定律揭示了信息技術進步的速度，為半導體行業(yè)的發(fā)展提供了長期的發(fā)展目標和預測。

二、時間復雜度

2.1 時間復雜度的概念

????????在計算機科學中，算法的時間復雜度是一個函數(shù)（這里的函數(shù)不是之前寫的函數(shù)調用的那個函數(shù)，而是數(shù)學中的函數(shù)式），它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。即：找到某條基本語句與問題規(guī)模N之間的數(shù)學表達式，就是算出了該算法的時間復雜度。（時間復雜度越大，運行水時間越長）。

? ? ? ? 但是我們?yōu)槭裁床恢苯佑懻摽焖倥判驁?zhí)行多少時間、冒泡排序執(zhí)行多少時間呢？原因在于具體怎么執(zhí)行與自己的機器（硬件）有關，硬件配置不一樣，就不能比較具體執(zhí)行的時間。因此，我么需要一套與環(huán)境因素（如硬件因素）無關的理論，也就是這里的時間復雜度。

請觀察下面的代碼，然后進行分析：

/********請計算一下Func1中++count語句總共執(zhí)行了多少次？*********/
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 執(zhí)行的基本操作次數(shù) ：F（N）=N^2+2*N+10
N = 10? ? ? ? ? ? ? F(N) = 130，? ? ? ? ? ? N^2 = 100
N = 100? ? ? ? ? ? F(N) = 10210,? ? ? ? ? ?N^2 = 10000
N = 1000? ? ? ? ? F(N) = 1002010,? ? ? ?N^2 = 1000000

? ? ? ? 從這個例子我們發(fā)現(xiàn)，當N越大（當N趨于無窮大時）,N^2對時間復雜度的結果影響最大。因此，我們選擇大概估算（大O的漸進表示法）的方法，忽略掉2*N+10這一項，時間復雜度就可以表示為：F（N）=O（N^2）。當N很小的時候，認為時間復雜度一樣，沒有比較的意義，CPU主頻很大。（CPU主頻在 2.3 有詳細介紹）

2.2 大O的漸進表示法

????????大概估算是計算算法屬于哪個量級（level）。

? ? ? ? 大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學符號。
推導大O階方法：
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結果就是大O階。
使用大O的漸進表示法以后，Func1的時間復雜度為：F（N）=O（N^2）
????????N = 10 F(N) = 100
????????N = 100 F(N) = 10000
????????N = 1000 F(N) = 1000000

????????通過上面的分析，我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。
????????另外有些算法的時間復雜度存在最好、平均和最壞情況：
?最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
?平均情況：任意輸入規(guī)模的期望運行次數(shù)
?最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)
例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x
?最好情況：1次找到
?最壞情況：N次找到
?平均情況：N/2次找到
????????在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為O(N)。

2.3 為什么O（n）使用最壞情況下的估算結果呢？

?????????在這種情況下，實際的結果要么就是估算的結果的驚喜，要么就剛好是最低預期結果，這是一種以防萬一的心態(tài)，在預估了所有壞的可能后得到的方案。

2.4?CPU主頻（拓展）

CPU主頻，也稱為時鐘頻率或時鐘速度，是指中央處理單元(CPU)內部時鐘的頻率或速度。

????????它表示了處理器每秒鐘執(zhí)行指令的次數(shù)，通常以赫茲(Hz)為單位表示，例如兆赫茲(MHz)或千兆赫茲(GHz)。主頻是評估其性能和速度的一個重要指標之一。一般來說，較高的主頻意味著處理器能夠更快地執(zhí)行指令，因此在一定程度上具有更高的性能。然而，主頻并不是評估處理器性能的唯一因素，其他因素如微架構、核心數(shù)量、緩存大小、指令集等也會影響性能。需要注意的是，主頻并不是唯一影響處理器性能的因素。不同型號的處理器可能在相同主頻下表現(xiàn)出不同的性能，因為它們的架構和其他規(guī)格可能不同。因此，在選擇計算機或處理器時，不僅要考慮主頻，還要綜合考慮其他因素，以確保滿足你的性能需求。

（資料來自百度）

CPU主頻也叫時鐘頻率，單位是MHz，用來表示CPU的運算速度。

????????CPU的工作頻率（主頻）包括兩部分：外頻與倍頻，兩者的乘積就是主頻。

????????倍頻的全稱為倍頻系數(shù)。CPU的主頻與外頻之間存在著一個比值關系，這個比值就是倍頻系數(shù)，簡稱倍頻。倍頻可以從1.5一直到23以至更高，以0.5為一個間隔單位。外頻與倍頻相乘就是主頻，所以其中任何一項提高都可以使CPU的主頻上升。由于主頻并不直接代表運算速度，所以在一定情況下，很可能會出現(xiàn)主頻較高的CPU實際運算速度較低的現(xiàn)象。因此主頻僅僅是CPU性能表現(xiàn)的一個方面，而不代表CPU的整體性能 。

????????處理器主頻以每秒處理器周期可運行的百萬次計算。通常，具有較高MHz或GHz的處理器能夠提高電腦運行創(chuàng)新、娛樂、通信和生產(chǎn)力應用的性能。但主頻只是影響系統(tǒng)整體性能的一個方面，主頻高的機器整體性能并非就一定高。
? ? ? ? ? ? ? ? ? ? ? ??
（聲明：此段文本復制自博客：http://t.csdnimg.cn/FGGi7）

????????簡而言之，CPU主頻反映了在一個周期內大概能執(zhí)行多少指令主頻越高，CPU的處理速度越快。CPU性能再怎么差，它每秒的運算速度也能運行上億次。可以利用clock函數(shù)驗證：

#include <time.h>int main()
{int begin1 = clock();int n = 100000000;int x = 10;for (int i = 0; i < n; i++){++x;}int end1 = clock();printf("%d\n", x); printf("程序運行時間%d ms\n", end1 - begin1);return 0;
}

?

如果結果為0ms說明中間的時間消耗小于1ms，而不是沒有時間消耗。

????????C語言中的函數(shù)clock()，它可以捕捉從程序開始運行到clock()被調用時所耗費的時間。兩個clock()函數(shù)的返回值相減，就可以計算兩個函數(shù)之間的程序運行所消耗的大概時間(ms)了。我么可以利用它來大致測試一下電腦的性能。而且，release版本做了優(yōu)化，因此時間比Debug版本稍短。

?

2.5?常見的時間復雜度量級

2.6?重要時間復雜度計算

2.6.1 冒泡排序的時間復雜度?O（n^2）

????????F（n）=（n-1）+ (n-2) + (n-3)+……+3+2+1=n*（n-1）/2 （可以根據(jù)兩個數(shù)比較的次數(shù)來寫）, 時間復雜度為：O（n^2）。注意不能直接數(shù)循環(huán)的個數(shù)。

// 計算BubbleSort的時間復雜度？
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;}
}

2.6.2?qsort函數(shù)的時間復雜度O（n*logn）

qsort函數(shù)的時間復雜度為： O（n*logn）

2.6.3 二分查找的時間復雜度

????????折半查找：n，n/2，n/2/2，……，n/2/2/……/2（查找了x次就除以x個2）,2^x=N，所以x=logN（省略底數(shù)2）。最壞情況：查找區(qū)間只剩一個數(shù)或者找不到。O（logN）

// 計算BinarySearch的時間復雜度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號 //保持左閉右閉區(qū)間（保持不變）while (begin <= end)//begin=end，還有一個數(shù){int mid = begin + ((end - begin) >> 1);//此寫法可以防止溢出if (a[mid] < x)begin = mid + 1;//因為簽】前一次比較中，mid已經(jīng)比較過了else if (a[mid] > x)end = mid - 1;//end是mid-1elsereturn mid;}return -1;
}//寫法二：
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;// [begin, end)  ->保持左閉右開區(qū)間while(begin<end){//int mid = begin + ((end - begin) >> 1);//防止溢出（begin+end值可能很大）//也可以寫成int mid = (begin + end)/2;(不能防止溢出)if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;//這里變成end=mid,而不是 mid-1elsereturn mid;}return -1;
}

????????二分查找：O（logN），隨著N的增長，O（logN）變化不大；暴力查找：O（N），隨著N的增長，O（N）變化很大。

? ? ? ? 缺點：二分查找外強中干，在實際中不太實用，需要排序、而且數(shù)組結構不方便插入刪除數(shù)據(jù)（會造成數(shù)據(jù)整體的挪動）。

2.6.4? strchr函數(shù)的時間復雜度

// 計算strchr的時間復雜度？
const char * strchr ( const char * str, int character );

????????在一個字符串中查找一個字符，它的實現(xiàn)過程就相當于如下的代碼：

while (*str)
{if (*str == character)return str;else++str;
}

????????最好情況：O（1），最壞情況：O（n），平均情況：O（（1+2+3+……+n）/n））。所以時間復雜度為O（n）。

????????時間復雜度的意義：幫助我們對比幾種解決方法孰優(yōu)孰劣。?

三、?常見時間復雜度的舉例

1、O（n）只看循環(huán)次數(shù)，且系數(shù)對結果影響不大

????????F（n）=2*n+10 , O（n）而不是O（2*n）。F（n）相當于只看循環(huán)次數(shù),要去掉系數(shù)2（即使這個系數(shù)是200也要去掉）,系數(shù)對結果影響不大，n無窮大時，n和2*n沒有區(qū)別。

// 計算Func2的時間復雜度？
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);
}

2、O（n）可以用多個未知數(shù)表示

????????F（n）=M+N,? O（M+N）或O（max(M,N)。在時間復雜度，經(jīng)常使用N作為未知數(shù)，也可以使用其它符號來表示未知數(shù)。如果M遠大于N，O(M)；如果如果N遠大于M，O(N)。不一定只有一個未知數(shù)。

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

3、F（n）= 常數(shù),? O（1）

? ? ? ? 時間復雜度是O（1），而不是O（100）。沒有未知數(shù)而只有常數(shù)次，則時間復雜度為? O（1）。

// 計算Func4的時間復雜度？
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}

4、單身狗題目回顧（為下一道題做鋪墊）

5、力扣--17.04. 消失的數(shù)字

????????題目描述：數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個。請編寫代碼找出那個缺失的整數(shù)。你有辦法在O(n)時間內完成嗎？

思路1：先排序（冒泡排序、qsort快速排序）再查找，如果前一個值(b)不等于后一個值(a) +1，那么前一個值(b)就是消失的數(shù)字。（由于時間復雜度，現(xiàn)可以直接拋棄該思路）（排序：a，b; a+1==b），但時間復雜度不符合要求。

思路2：先將0~N進行求和，然后再依次減去數(shù)組中值，剩下的值就是消失的數(shù)字。時間復雜度為O（N）。（缺陷：N太大，存在溢出風險）

int missingNumber(int* nums, int numsSize){int N = numsSize;//0~n一共n+1個數(shù)，但缺了1個數(shù)，一共n個數(shù)int ret = (0 + N) * (N + 1) / 2;//計算出0~n的總和for(int i = 0; i < numsSize; ++i)//{ret -= nums[i];//總和減去數(shù)組中值}return ret;
}

思路3：按位異或（相同為0，相異為1）（有點類似于單身狗的那道題）。O（n）

int missingNumber(int* nums, int numsSize){int N = numsSize;int x = 0;for(int i = 0; i < numsSize; ++i)//numsSize是少了1的，9個數(shù){x ^= nums[i];//0和任何數(shù)異或均是任何數(shù)}  for(int j = 0; j <= N; ++j)//這里有n個數(shù)，10個數(shù){x ^= j;}return x;
}

6、力扣--189. 輪轉數(shù)組

????????題目描述：給定一個整數(shù)數(shù)組?nums，將數(shù)組中的元素向右輪轉?k?個位置，其中?k?是非負數(shù)。?

分析：需要一個循環(huán)兩個嵌套，時間復雜度應該是：O（k*N）。

思路1：暴力求解（用只管的方式直接解 決問題，不用太多技巧）

????????表達式為：F（N）= （N-1）*（N-1）；O（k * N）

????????如果k為7或者7的倍數(shù)次,旋轉7次或者7的倍數(shù)次，其實就是旋轉到原來的樣子（相當于不旋轉）；如果旋轉10次，就相當于旋轉了3次。所以真實的旋轉次數(shù)為 k % = N ;在最好情況下，即沒有旋轉，k % N = 0 , O（1）;在最壞情況下K（N）=N*(N-1)， k % N = N-1，O（N^2）,旋轉N-1次，。

????????值得注意的是：時間復雜度必須要計算調用的其它方法所花的時間消耗。

void rotate(int* nums, int numsSize, int k) 
{k%=numsSize;while(k--)//k最大為n-1，k--走了k次，所以這里走了n-1次{//旋轉一次      畫圖是最好的分析方法int tmp = nums[numsSize-1];//最后一個數(shù)保存起來for(int i =numsSize-2;i >= 0;i--)//起始位置在n-2（numsSize-2），結束情況：i >= 0{nums[i+1] = nums[i];//中間過程}nums[0] = tmp;}//但是用這種方法不能通過，超出時間限制（不能O（N^2））
}//前n-1個數(shù)往后挪
//循環(huán)分析：循環(huán)就三個過程，起始情況、中間過程、結束情況

????????思路2：三段逆置? O（N）

代碼如下：?

void reverse(int*  a,int left,int right)
{//三段逆置一定要畫圖,下標標明while(left<right)//一段區(qū)間，左右往中間走，未相遇，交換值{int tmp =a[left];a[left] = a[right];a[right] = tmp;++left;--right;}
}void rotate(int* nums, int numsSize, int k) {k%= numsSize;reverse(nums,0,numsSize-k-1);//前n-k個數(shù)，最后一個下標n-k-reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}

strncpy是針對字符串的，在這里不合適。
?

7、對數(shù)時間復雜度常見出現(xiàn)形式

????????時間復雜度O（logN）

void func(int n)
{int x = 0;for (int i = 1; i < n; i *= 2){++x;}printf("%d\n", x);
}
int main()
{func(8);func(1024);func(1024*1024);return 0;
}

????????分析：1*2*2*……*2 = N；假設循環(huán)走x次，就是x個2相乘，2^x=N，兩邊同時取對數(shù)，得到?。時間復雜度就是O（）。因為寫的時候需要支持專業(yè)公式，否則不好寫底數(shù)。為了方便?省略了底數(shù)2，直接寫成了，但是其他的就不能省略且其他底數(shù)的很少出現(xiàn)。

8、階乘遞歸的時間復雜度

// 計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}

????????每次調用函數(shù)都是O（1）的復雜度，調用N次就是O（N）的復雜度，而不是O（N！）。如果變式：時間復雜度為O（N^2）。?

//變式：
// 計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{if(0 == N)return 1;for(int i = 0; i <N;++i){//……}return Fac(N-1)*N;
}

????????總結：遞歸時間復雜度為所有遞歸調用消耗次數(shù)（相當于運算次數(shù)）的累加。

9、斐波那契遞歸和非遞歸的時間復雜度

????????斐波那契遞歸非遞歸的時間復雜度O（N^2）

// 計算斐波那契遞歸Fib的時間復雜度？
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}

????????最左側會逐步減少到Fib（1），有N層，但是右側未必能走到N層，所以呈現(xiàn)的三角形并不是等腰三角形，但是不影響最終的量級，大O階表示時間復雜度O（N^2）?。分析過程如下圖：

?????????斐波那契非遞歸（斐波那契數(shù)列的優(yōu)化）的時間復雜度 ：

// 1  1  2  3  5  8....
// 時間復雜度：O(N)（很大的優(yōu)化）
long long Fib(size_t N)
{long long f1 = 1;long long f2 = 1;long long f3 = 0;for (size_t i = 3; i <= N; i++){f3 = f1 + f2;f1 = f2;f2 = f3;}return f3;
}

? ? ? ? 其實斐波那契數(shù)列沒什么特別的實用意義，因為數(shù)據(jù)稍稍大點就計算不出結果了。（50都不得行了）。此外，還可以使用字符串進行存儲（大樹運算）。

四、空間復雜度

4.1 空間復雜度定義?

????????空間復雜度也是一個數(shù)學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度?
????????空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)?？臻g復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。
????????注意：函數(shù)運行時所需要的?？臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。

4.2 空間復雜度例題

? ? ? ? 1、冒泡排序的空間復雜度

????????變量個數(shù)：3（常數(shù)個），所以空間復雜度為O（1）?？臻g復雜度計算的是為了解決這個問題而額外初選的空間 ，因此此算法中的數(shù)組不計算空間。

// 計算BubbleSort的空間復雜度？
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;}
}

?????????2、? 輪轉數(shù)組另一個解法（空間復雜度）

????????不用三段逆置的方法，重新創(chuàng)建一個數(shù)組，后k個旋轉在前面，再把前n-k個拷貝到后面去 ，最后再將最終結果拷貝到原來的位置。此時，新創(chuàng)建的N個數(shù)組就是為了解決此問題而創(chuàng)建的，它就需要計算空間，空間復雜度就是O（N）。

最后的代碼如下，代碼中使用了變長數(shù)組：

void _rotate(int* nums, int numsSize, int k, int* tmp)
{k %= numsSize;int n = numsSize;memcpy(tmp, nums + n - k, sizeof(int) * k);memcpy(tmp+k, nums, sizeof(int) * (n-k));memcpy(nums,tmp, sizeof(int) * (n));
}void rotate(int* nums, int numsSize, int k)
{int tmp[numsSize];_rotate(nums, numsSize, k, tmp);
}

????????3、階乘遞歸的空間復雜度

// 計算階乘遞歸Fac的空間復雜度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

4、斐波那契數(shù)列的空間復雜度為：

?????????常見的空間復雜度中只有三種：O（1）、O（N）、O（N^2）（比如二維數(shù)組）。

? ? ? ? 創(chuàng)作不易，喜歡的uu三連支持一下叭！?