前言
在算法的世界里，效率是衡量算法優劣的關鍵標準。今天，就讓我們深入探討算法效率的兩個核心維度：時間復雜度和空間復雜度，幫助你在算法設計的道路上更進一步。
一、算法效率：衡量算法好壞的關鍵
算法的效率主要體現在兩個方面：時間和空間。時間復雜度衡量的是算法運行的快慢，而空間復雜度則衡量算法運行所需的額外空間。在計算機發展的早期，存儲容量有限，空間復雜度備受關注。然而，隨著計算機存儲容量的飛速發展，如今我們更關注算法的時間復雜度。
1.1 斐波那契數列：一個經典的例子
斐波那契數列是一個經典的算法問題。其遞歸實現方式簡潔明了，但這種簡潔性是否意味著它是一個好的算法呢？答案并非絕對。遞歸實現雖然代碼簡潔，但其時間復雜度較高，對于較大的輸入值，運行時間會顯著增加。這正是我們需要深入分析算法復雜度的原因。
long long Fib(int N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
二、時間復雜度：算法運行快慢的量化
時間復雜度是衡量算法運行時間的函數。它通過分析算法中基本操作的執行次數來確定。在實際中，我們通常使用大O的漸進表示法來簡化復雜度的表達。
2.1 大O的漸進表示法
大O符號（Big O notation）是描述函數漸進行為的數學符號。推導大O階的方法如下：
用常數1取代運行時間中的所有加法常數。
在修改后的運行次數函數中，只保留最高階項。
如果最高階項存在且不是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;}
}
通過計算，我們發現基本操作++count的執行次數為 N^ 2+2*N+10。使用大O的漸進表示法，我們去掉常數項和低階項，得到時間復雜度為 O(N ^2 )。
2.2 常見時間復雜度計算舉例
讓我們通過一些實例來進一步理解時間復雜度的計算。
實例1
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}
}
基本操作執行了 2N+10 次，時間復雜度為 O(N)。
實例2
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;}
}
基本操作執行了 M+N 次，時間復雜度為 O(N+M)。
實例3
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}
}
基本操作執行了10次，時間復雜度為 O(1)。（O（1）不是代表一次，而是代表常數次）
實例4
const char *strchr(const char *str, int character);while(*str)
{if(*str == character)return str;str++;
時間復雜度為 O(N)。(一般以最壞情況作為時間復雜度）
實例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;}
}
時間復雜度為 O(N^2 )。（最好：O（N），最壞：O（N ^ 2)）
實例6（有序 經典二分查找）
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;elsereturn mid;}return -1;
}
時間復雜度為 O(logN)。（最好：O（1），最壞：O（logN）區間縮放到一個值時，要么找到，要么找不到，折半查找多少次（x）就除多少個2。2^x=N）
三、空間復雜度：算法所需額外空間的量化
空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。它主要通過函數在運行時顯式申請的額外空間來確定。
3.1 空間復雜度計算實例
實例1
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}
Fac(N)
Fac(N-1)
Fac(N-2)
...
Fac(1)
Fac(0)
空間復雜度為 O(N)。
實例2
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;
}
空間復雜度為 O(N)。
實例3
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
2^0 Fib(N)2^1Fib(N-1) Fib(N-2)2^2 Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-2)...2^(N-1)Fib(2) Fib(1)
空間復雜度為 O(2^N)。
四、常見復雜度對比
常見的復雜度從低到高依次為：O(1)、O(logN)、O(N)、O(NlogN)、O(N^2 )、O(2 ^N )、O(N!)。選擇合適的算法，可以顯著提升程序的運行效率。
五、復雜度的OJ練習
理論學習之后，通過實踐來鞏固知識是必不可少的。以下是一些推薦的OJ題目：
消失的數字
參考：
1.
2.
旋轉數組
總結
時間復雜度和空間復雜度是算法設計中不可或缺的兩個維度。通過深入理解它們，我們可以更好地選擇和設計高效的算法。希望這篇文章能幫助你更好地掌握算法效率的分析方法，讓你在算法學習的道路上更進一步。
