目錄
前言
演算法效率
時間復雜度
大O的漸進表示法
常見時間復雜度計算舉例
空間復雜度
常見空間復雜度計算舉例
前言
本章主要講解：
- 時間復雜度和空間復雜度的講解
- 常見的復雜度相關練習
演算法效率
演算法運行時需要耗費時間資源和空間(記憶體)資源
- 衡量一個演算法的好壞標準：
一般是從時間和空間兩個維度來衡量的時間復雜度主要衡量一個演算法的運行快慢而空間復雜度主要衡量一個演算法運行所需要的額外空間
注：現在已經不特別關注一個演算法的空間復雜度（科技發展/摩爾定律）
時間復雜度
- 概念：
演算法的時間復雜度是一個函式，定量描述了該演算法的運行時間這里不是演算法執行所耗費的實際時間，而是演算法中的基本操作的執行次數找到某潭訓本陳述句與問題規模N之間的數學運算式，就是算出了該演算法的時間復雜度
注：實際計算時間復雜度不一定要計算精確的執行次數，只需要大概執行次數（大O的漸進表示法）
大O的漸進表示法
大O符號（Big O notation）用于描述函式漸進行為的數學符號
- 推導大O階方法：
- 用常數1取代運行時間中的所有加法常數
- 在修改后的運行次數函式中，只保留最高階項
- 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階
- 簡單來說：
大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數
- 示例：
void Func(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);
}執行的基本操作次數：
大O的漸進表示法:
- 注意：
在實際中有些演算法的時間復雜度存在最好、平均和最壞情況，一般情況關注的是演算法的最壞運行情況
- 示例：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到最壞情況：N次找到平均情況：N/2次找到
該陣列中搜索資料時間復雜度為：O(N)
常見時間復雜度計算舉例
- 示例1：
void Func1(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
時間復雜度為：O(N)
- 示例2：
void Func2(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+M)
- 示例3：
void Func3(int N) {
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}時間復雜度為：O(1)
注：并不是執行一次，而是表示常數次
- 示例4：
// 計算strchr的時間復雜度？
//在字串找字符，找到則回傳對應地址（類似于遍歷演算法）
const char * strchr ( const char * str, int character );時間復雜度為：O(N)
- 示例5：
// 計算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;
}
}執行次數運算式：n-1+n-2+n-3+...+1=n（n-1）/2（等差求和）
時間復雜度為：O(N^2)
- 示例6:
// 計算BinarySearch的時間復雜度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
while (begin < end)
{
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;
}執行次數表達：
注：x為最差情況下的查找次數，N為陣列長度
反向思考：從找到開始回推，每回推一次個數x2，經過x次最后總個數為陣列總長度
時間復雜度為：
- 示例7：
// 計算階乘遞回Fac的時間復雜度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
執行次數運算式：n
時間復雜度為：O(N)
- 示例8：
// 計算斐波那契遞回Fib的時間復雜度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
注：實際上右邊的呼叫會比左邊更快結束，即右邊會缺一些項
執行次數運算式：(等比求和，C為常數)
時間復雜度為：
空間復雜度
- 概念：
空間復雜度也是一個數學運算式，是對一個演算法在運行程序中臨時占用存盤空間大小的量度空間復雜度不是計算程式占用了多少bytes的空間，而是變數的個數空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法
注：函式運行時所需要的堆疊空間(存盤引數、區域變數、一些暫存器資訊等)在編譯期間已經確定好了，因此空間復雜度主要通過函式在運行時候顯式申請的額外空間來確定
常見空間復雜度計算舉例
- 示例1：
// 計算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;
}
}
注：使用了常數個額外空間
空間復雜度為 ：O(1)
- 示例2：
// 計算Fibonacci的空間復雜度？
// 回傳斐波那契數列的前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;
}
注：空間復雜度看的是額外的空間消耗，當斐波那契數列分支呼叫到頭時開始回傳，回傳會銷毀函式堆疊幀，所以最多額外開辟N個函式堆疊幀（空間）
空間復雜度為： O(N)
- 示例3：
// 計算階乘遞回Fac的空間復雜度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}注：遞回呼叫了N次，額外開辟N個函式堆疊幀（空間）
空間復雜度為：O(N)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/323437.html
標籤：其他