目錄
一、什麼是時間複雜度和空間複雜度？
1.算法效率
2.時間複雜度的概念
3.空間複雜度的概念
4.複雜度計算在算法的意義
二、如何計算常見算法的時間複雜度？
推導大O階方法
複雜度對比
三、典型複雜度要求的算法題練習
執行個體1
執行個體2
執行個體3
執行個體4
執行個體5：二分查找
執行個體6：單路遞歸
執行個體7：多路遞歸
結語
【前言】：前天有位鐵汁建議我更新資料結構這塊内容，原本我是打算放到兩個月之後的，不過呢那位老鐵是真的迫切，但是我精力有限，是以昨天晚上我認真想了一下，決定把零基礎搞定C語言系列壓縮一下，也就是說，C語言就不每個知識點都講一遍了，畢竟CSDN中有很多關于C語言優秀的文章，是以我直接把我認為重要的，以及一些易錯點寫出來，再夾帶着一些筆試題，這樣的話時間稍微充裕些。
【聲明】：資料結構已經拉開序幕咯，可能有點晚，但是筆者會盡量跟上的哦，鐵汁們上車了沒！？
嘿嘿，鐵汁們的要求我會盡量滿足的，不負代碼不負卿哦！
一、什麼是時間複雜度和空間複雜度？
1.算法效率
算法效率分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度， 而空間效率被稱作空間複雜度。 時間複雜度主要衡量的是一個算法的運作速度，而空間複雜度主 要衡量一個算法所需要的額外空間，在計算機發展的早期，計算機的存儲容量很小。是以對空間 複雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。 是以我們如今已經不需要再特别關注一個算法的空間複雜度。
前面巴拉巴拉贅述了這麼多，我們隻需要知道，算法效率分為兩種：一是時間效率，二是空間效率；時間效率被稱為時間複雜度， 而空間效率被稱作空間複雜度。
2.時間複雜度的概念
時間複雜度的定義：在計算機科學中，算法的時間複雜度是一個函數，它定量描述了該算法的運 行時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，隻有你把你的程式放在機 器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻 煩，是以才有了時間複雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比 例，算法中的基本操作的執行次數，為算法的時間複雜度。
【敲黑闆】：算法中基本操作的執行次數，為算法的時間複雜度。
3.空間複雜度的概念
空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的量度 。空間複雜度不是程式占用 了多少bytes的空間，因為這個也沒太大意義，是以空間複雜度算的是變量的個數
【敲黑闆】：空間複雜度算的是變量的個數
注意注意，一定要注意：時間複雜度算的不是時間，算的是基本操作的執行次數；空間複雜度算的不是空間，算的是變量的個數。
4.複雜度計算在算法的意義
其實很多公司在招聘的時候，資料結構和算法這塊是考察的重點，在算法筆試題裡面幾乎都會考察應聘者對複雜度的計算和了解。是以，鐵汁們，這塊内容雖然不難，但卻是重點哦，不能掉以輕心！上面難了解或者是容易想錯的地方都已經明确标記出來咯，抓緊時間記住哈。加油加油！！
二、如何計算常見算法的時間複雜度？
【敲黑闆】：實際中我們計算時間複雜度時，我們其實并不一定要計算精确的執行次數，隻需要大概執行次數，那麼這裡我們使用大O的漸進表示法。
大O符号（Big O notation）：是用于描述函數漸進行為的數學符号。
推導大O階方法
1、用常數1取代運作時間中的所有常數。
2、在修改後的運作次數函數中，隻保留最高階項，去除那些對結果影響不大的項
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。
得到的結果就是大O階，是以大O的漸進表示法隻是一個估算。
可能你不是很了解上面推導大O階方法，沒關系，下面給出幾道例題，你很快就能了解啦！
//計算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--)
{
count++;
}
} Func1()基本操作的執行次數：
F(N) = N ^ 2 + 2 * N + 10 ;
随着N的增大，N ^ 2對結果的影響是最大的
而時間複雜度隻是一個估算，是以僅僅取決于表達式中對結果影響最大的那一項
是以，本題的時間複雜度為 O(N ^ 2)
另外有些算法的時間複雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運作次數(上界)；
平均情況：任意輸入規模的期望運作次數；
最好情況：任意輸入規模的最小運作次數(下界)。
例如：在一個長度為N數組中搜尋一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是算法的最壞運作情況，是以數組中搜尋資料時間複雜度為O(N）
複雜度對比
深度剖析基礎資料結構系列第一章——開胃小菜之複雜度 O(1)是最好的，其次是O(logN)...
常見的時間複雜度：
O(N) O(N ^ 2) O(log N) O(1)
而空間複雜度就不像時間複雜度這麼複雜了，一般情況下空間複雜度都是O(1)，因為時間是累計的，而空間卻不是累計的。比如循環走了n次，其實利用的是一個空間，因為變量往回走的時候，就會銷毀原先開辟的空間，現在暫時不了解也沒有關系，後面有大量的練習呢。
三、典型複雜度要求的算法題練習
執行個體1
void Func2(int n)
{
int count = 0;
for (int k = 0; k < 2 * n; k++)
{
count++;
}
int m = 10;
while (m--)
{
count++;
}
} Func2()基本操作的執行次數：
F(N) = 2 * N + 10
随着N的增大，2 * N 對結果的影響是最大的，又因為其系數不是1，是以要去除與N相乘的常數2
是以，本題的時間複雜度為：O(N)
執行個體2
int Func(int n, int m)
{
int count = 0;
for (int k = 0; k < m; k++)
{
count++;
}
for (int i = 0; i < n; i++)
{
count++;
}
} Func3()基本操作的執行次數：
F(N) = m + n
如果說明m 遠大于 n, 則時間複雜度為O(M)；
如果說明m 約等于 n, 則時間複雜度為O(N)；
如果沒有說明，則時間複雜度為O(M + N)
執行個體3
void Func4(int n)
{
int count = 0;
for (int k = 0; k < 100; k++)
{
count++;
}
} 可能你以為是O(100)，但是不是哦，是O(1)
執行個體4
const char* strchr(const char* str, char character)
{
while (*str != '\0')
{
if (*str != character)
{
return str;
}
str++;
}
return NULL;
} 假設字元串的長度為N，則本題時間複雜度為O(N)
執行個體5：二分查找
前提：數組是有序的！！
int Binary_search(int* arr, int n, int k)
{
int left = 0;
int right = n - 1;
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] > k)
{
right = mid - 1;
}
else if (arr[mid] < k)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
} 想象一張電費條：長度為n (n / 2^0)
第一次砍一半剩：n / 2 (n / 2^1)
第二次砍一半剩：n / 4 (n / 2^2)
第三次砍一半剩：n / 8 (n / 2^3)
...
假設砍了x次找到了：n / 2^x = 1
是以有，2^x = n ---> x = log n
是以二分查找的時間複雜度為：O(logN)
執行個體6：單路遞歸
int func(int n)
{
if (n == 1)
{
return 1;
}
return n + func(n - 1);
} 遞歸調用了n次，每一次遞歸運算的時間複雜度為O(1)，是以n次就是O(N)；
但是要注意的是，本題的空間複雜度不再是O(1)。
這裡就需要補充一下遞歸函數調用的知識點了，每次調用遞歸函數都需要建立一個棧幀，而每個棧幀又都使用了常數個空間，遞歸函數的空間複雜度取決于遞歸調用棧的深度，是以很明顯，本題空間複雜度為O(N)
【敲黑闆】：遞歸函數調用時建立棧幀，傳回時銷毀。
執行個體7：多路遞歸
斐波那契數列遞歸：
題目描述：求斐波那契數列的第N項，1 1 2 3 5 8 13 21...
int fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return fib(n - 1) + fib(n - 2);
} 本題非常典型，屬于多路遞歸，可以将它畫成二叉樹的形式：
但是求時間複雜度的時候，我們要的是最壞的情況，是以假設成滿二叉樹，時間複雜度就是該二叉樹節點的個數，也就是O(2^N);
空間複雜度為這棵樹的高度，是以是O(N)