演算法基礎概念
概念
1. 運算
2. 排序
3. 查找
4. 在電腦領域裡，演算法是一系列程式指令，用於處理特定的運算和邏輯問題。衡量演算法優劣的主要標準是時間複雜度和空間複雜度。
時間複雜度（計算程式碼運行的時間成本）
1.運行的時間長度
2.基本操作執行次數
3.基本操作執行次數的函數 T(n)
**漸進時間複雜度**
若存在函數 f(n)，使得當 n 趨近於無窮大時，T(n)/f(n) 的極限值為不等於零的常數，則稱 f(n) 是 T(n) 的同數量級函數。記作 T(n)=O(f(n))，稱為 O(f(n))，O 為演算法的漸進時間複雜度，簡稱為時間複雜度。因為漸進時間複雜度用大寫 O 來表示，所以也被稱為 大 O 表示法
4.如何推導出時間複雜度呢？有如下幾個原則。
- 如果運行時間是常數量級，則用常數 1 表示
- 只保留時間函數中的最高階項
- 如果最高階項存在，則省去最高階項前面的係數
5.時間複雜度是對一個演算法運行時間長短的量度，用大 O 表示，記作 T(n)=O(f(n))。常見的時間複雜度按照從低到高的順序，包括 O(1)、O(log n)、O(n)、O(n log n)、O(n^2)等
空間複雜度（計算程式碼運行的空間成本）
1.程式佔用空間大小的計算公式記作 S(n)=O(f(n))，其中 n 為問題的規模，f(n) 為演算法所佔存儲空間的函數
2.常見的空間複雜度有下面幾種情形
常量空間：當演算法的存儲空間大小固定，和輸入規模沒有直接的關係時，空間複雜度記作 O(1)
線性空間：當演算法分配的空間是一個線性的集合（如數組），並且集合大小和輸入規模 n 成正比時，空間複雜度記作 O(n)
二維空間：當演算法分配的空間是一個二維數組集合，並且集合的長度和寬度都與輸入規模 n 成正比時，空間複雜度記作 O(n^2)
遞歸是一個比較特殊的場景。雖然遞歸程式碼中並沒有顯式地聲明變數或集合，但是電腦在執行程式時，會專門分配一塊記憶體，用來存儲「方法調用棧」。
遞歸空間：「方法調用棧」包括進棧和出棧兩個行為。當進入一個新方法時，執行入棧操作，把調用的方法和參數資訊壓入棧中。當方法返回時，執行出棧操作，把調用的方法和參數資訊從棧中彈出，最終，「方法調用棧」的全部元素會一一出棧
由上面「方法調用棧」的出入棧過程可以看出，執行遞歸操作所需要的記憶體空間和遞歸的深度成正比。純粹的遞歸操作的空間複雜度也是線性，如果遞歸的深度是 n，那麼空間複雜度就是 O(n)
空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，用大 O 表示，記作S(n)=O(f(n))。常見的空間複雜度按照從低到高的順序，包括O(1)、O(n)、O(n^2)等。其中遞歸演算法的空間複雜度和遞歸深度成正比
