在學習具體的資料結構和算法之前，每一位初學者都要掌握一個技能，即善于運用時間複雜度和空間複雜度來衡量一個算法的運作效率。
所謂算法，即解決問題的方法。同一個問題，使用不同的算法，雖然得到的結果相同，但耗費的時間和資源肯定有所差異。就比如擰一個螺母，扳手和鉗子都可以勝任，但使用鉗子擰螺母肯定沒有扳手的效率高。
圖 1 解決問題的方式有多種
這也就意味着，如果解決問題的算法有多種，我們就需要從中選出最好的那一個。那麼，怎麼判斷哪個算法更好（或者更優）呢？
“好”算法的标準
解決一個問題的方法可能有很多，但能稱得上算法的，首先它必須能徹底解決這個問題（稱為準确性），且根據其編寫出的程式在任何情況下都不能崩潰（稱為健壯性）。
注意，程式和算法是完全不同的概念。算法是解決某個問題的想法、思路；而程式是在根據算法編寫出來的真正可以運作的代碼。例如，要依次輸出一維數組中的資料元素的值，首先想到的是使用循環結構，在這個算法的基礎上，我們才開始編寫程式。
在滿足準确性和健壯性的基礎上，還有一個重要的篩選條件，即通過算法所編寫出的程式的運作效率。程式的運作效率具體可以從 2 個方面衡量，分别為：
- 程式的運作時間。
- 程式運作所需記憶體空間的大小。
根據算法編寫出的程式，運作時間更短，運作期間占用的記憶體更少，該算法的運作效率就更高，算法也就更好。
那麼，如何衡量一個算法所編寫出程式的運作效率呢？資料結構中，用時間複雜度來衡量程式運作時間的多少；用空間複雜度來衡量程式運作所需記憶體空間的大小。
時間複雜度
判斷一個算法所程式設計式運作時間的多少，并不是将程式編寫出來，通過在計算機上運作所消耗的時間來度量。原因很簡單，一方面，解決一個問題的算法可能有很多種，一一實作的工作量無疑是巨大的，得不償失；另一方面，不同計算機的軟、硬體環境不同，即便使用同一台計算機，不同時間段其系統環境也不相同，程式的運作時間很可能會受影響，嚴重時甚至會導緻誤判。
實際場景中，我們更喜歡用一個估值來表示算法所程式設計式的運作時間。所謂估值，即估計的、并不準确的值。注意，雖然估值無法準确的表示算法所程式設計式的運作時間，但它的得來并非憑空揣測，需要經過缜密的計算後才能得出。
也就是說，表示一個算法所程式設計式運作時間的多少，用的并不是準确值（事實上也無法得出），而是根據合理方法得到的預估值。
那麼，如何預估一個算法所程式設計式的運作時間呢？很簡單，先分别計算程式中每條語句的執行次數，然後用總的執行次數間接表示程式的運作時間。
以一段簡單的 C 語言程式為例，預估出此段程式的運作時間：
for(int i = 0 ; i < n ; i++) //<- 從 0 到 n，執行 n+1 次
{
a++; //<- 從 0 到 n-1，執行 n 次
}
可以看到，這段程式中僅有 2 行代碼，其中：
- for 循環從 i 的值為 0 一直逐增至 n（注意，循環退出的時候 i 值為 n），是以 for 循環語句執行了 n+1 次；
- 而循環内部僅有一條語句，a++ 從 i 的值為 0 就開始執行，i 的值每增 1 該語句就執行一次，一直到 i 的值為 n-1，是以，a++ 語句一共執行了 n 次。
是以，整段代碼中所有語句共執行了 (n+1)+n 次，即 2n+1 次。資料結構中，每條語句的執行次數，又被稱為該語句的頻度。整段代碼的總執行次數，即整段代碼的頻度。
再舉一個例子：
for(int i = 0 ; i < n ; i++) // n+1
{
for(int j = 0 ; j < m ; j++) // n*(m+1)
{
num++; // n*m
}
}
讀者可結合注釋，計算此段程式的頻度為：(n+1)+n*(m+1)+n*m，簡化後得 2*n*m+2*n+1。值得一提的是，不同程式的運作時間，更多場景中比較的是在最壞條件下程式的運作時間。以上面這段程式為例，最壞條件即指的是當 n、m 都為無限大時此段程式的運作時間。
要知道，當 n、m 都無限大時，我們完全就可以認為 n==m。在此基礎上，2*n*m+2*n+1 又可以簡化為 2*n2+2*n+1，這就是此段程式在最壞情況下的運作時間，也就是此段程式的頻度。
如果比較以上 2 段程式的運作時間，即比較 2n+1 和 2*n2+2*n+1 的大小，顯然當 n 無限大時，前者要遠遠小于後者（如圖 2 所示）。
圖 2 不同程式運作時間的比較
顯然，第 1 段程式的運作時間更短，運作更快。
思考一個問題，類似 2n+1、2*n2+2*n+1 這樣的頻度，還可以再簡化嗎？答案是肯定的。
以 2n+1 為例，當 n 無限大時，是否在 2n 的基礎上再做 +1 操作，并無關緊要，因為 2n 和 2n+1 當 n 無限大時，它們的值是無限接近的。甚至于我們還可以認為，當 n 無限大時，是否給 n 乘 2，也是無關緊要的，因為 n 是無限大，2*n 也是無限大。
再以無限大的思想來簡化 2*n2+2*n+1。當 n 無限大的：
- 首先，常數 1 是可以忽略不計的；
- 其次，對于指數級的 2*n2 來說，是否在其基礎上加 2*n，并無關緊要；
- 甚至于，對于是否給 n2 乘 2，也可以忽略。
是以，最終頻度 2*n2+2*n+1 可以簡化為 n2 。
也許很多讀者對于“使用無限大的思想”簡化頻度表達式，并不是很清楚。沒關系，這裡給大家總結一下，在資料結構中，頻度表達式可以這樣簡化：
- 去掉頻度表達式中，所有的加法常數式子。例如 2n2+2n+1 簡化為 2n2+2n ；
- 如果表達式有多項含有無限大變量的式子，隻保留一個擁有指數最高的變量的式子。例如 2n2+2n 簡化為 2n2；
- 如果最高項存在系數，且不為 1，直接去掉系數。例如 2n2 系數為 2，直接簡化為 n2 ；
事實上，對于一個算法（或者一段程式）來說，其最簡頻度往往就是最深層次的循環結構中某一條語句的執行次數。例如 2n+1 最簡為 n，實際上就是 a++ 語句的執行次數；同樣 2n2+2n+1 簡化為 n2，實際上就是最内層循環中 num++ 語句的執行次數。
得到最簡頻度的基礎上，為了避免人們随意使用 a、b、c 等字元來表示運作時間，需要建立統一的規範。資料結構推出了大 O 記法（注意，是大寫的字母 O，不是數字 0）來表示算法（程式）的運作時間。發展至今，此方法已為大多數人所采納。
大 O 記法的表示方法也很簡單，格式如下：
O(頻度)
其中，這裡的頻度為最簡之後所得的頻度。
例如，用大 O 記法表示上面 2 段程式的運作時間，則上面第一段程式的時間複雜度為 O(n)，第二段程式的時間複雜度為 O(n2)。
如下列舉了常用的幾種時間複雜度，以及它們之間的大小關系：
O(1)常數階 < O(logn)對數階 < O(n)線性階 < O(n2)平方階 < O(n3)(立方階) < O(2n) (指數階)
注意，這裡僅介紹了以最壞情況下的頻度作為時間複雜度，而在某些實際場景中，還可以用最好情況下的頻度和最壞情況下的頻度的平均值來作為算法的平均時間複雜度。
空間複雜度
和時間複雜度類似，一個算法的空間複雜度，也常用大 O 記法表示。
要知道每一個算法所編寫的程式，運作過程中都需要占用大小不等的存儲空間，例如：
- 程式代碼本身所占用的存儲空間；
- 程式中如果需要輸入輸出資料，也會占用一定的存儲空間；
- 程式在運作過程中，可能還需要臨時申請更多的存儲空間。
首先，程式自身所占用的存儲空間取決于其包含的代碼量，如果要壓縮這部分存儲空間，就要求我們在實作功能的同時，盡可能編寫足夠短的代碼。
程式運作過程中輸入輸出的資料，往往由要解決的問題而定，即便所用算法不同，程式輸入輸出所占用的存儲空間也是相近的。
事實上，對算法的空間複雜度影響最大的，往往是程式運作過程中所申請的臨時存儲空間。不同的算法所編寫出的程式，其運作時申請的臨時存儲空間通常會有較大不同。
舉個例子：
int n;
scanf("%d", &n);
int a[10];
通過分析不難看出，這段程式在運作時所申請的臨時空間，并不随 n 的值而變化。而如果将第 3 行代碼改為：
int a[n];
此時，程式運作所申請的臨時空間，和 n 值有直接的關聯。
是以，如果程式所占用的存儲空間和輸入值無關，則該程式的空間複雜度就為 O(1)；反之，如果有關，則需要進一步判斷它們之間的關系：
- 如果随着輸入值 n 的增大，程式申請的臨時空間成線性增長，則程式的空間複雜度用 O(n) 表示;
- 如果随着輸入值 n 的增大，程式申請的臨時空間成 n2 關系增長，則程式的空間複雜度用 O(n2) 表示；
- 如果随着輸入值 n 的增大，程式申請的臨時空間成 n3 關系增長，則程式的空間複雜度用 O(n3) 表示；
- 等等。
在多數場景中，一個好的算法往往更注重的是時間複雜度的比較，而空間複雜度隻要在一個合理的範圍内就可以。