算法的基本概念和要素
- 運算
- 查找
- 排序
- 最優(yōu)決策
數據結構
為了更高效地存儲、訪問和修改數據，數據結構就產生了。
- 線性結構
數組、鏈表（衍生——>棧、隊列、哈希表） - 樹
二叉樹、二叉堆等 - 圖
多對多的關聯關系 - 其他
由基礎的數據結構變形而來，為了解決某些特定的問題。（跳表、哈希鏈表、位圖）
時間復雜度
基本操作執(zhí)行次數
受運行環(huán)境 輸入規(guī)模的影響，程序運行的絕對執(zhí)行時間是無法確定的。
靈魂拷問：你還記得log2(下標)n嗎？
對數，以2為底，n的對數，也就是n要除以2多少次才能得到1。
程序執(zhí)行次數可能與輸入規(guī)模（n）存在一定的對應關系，如
- T(n) = 3n;
- T(n) = 5logn;
- T(n) = 3;
- T(n) = 3n^2 + 3n;
這就呈現了一定的對應關系。
那么3n 一定小于 5logn嗎？？
漸進時間復雜度
若存在f(n)使得當n無窮大時，T(n)/f(n)的極值為不為0的常數，則該f(n)是T(n)的同數量級函數。
T(n) = O(f(n))。這個O就是時間復雜度。他將相對時間函數T(n)簡化為一個數量級（n、n2、n3）
推導時間復雜度
- 如果運行時間為常數量級，則用1表示；
- 保留時間函數中的最高階項；
- 如果最高階存在，則省去前系數。
1、T(n) = 3n ——> T(n) = O(n);
2、T(n) = 5logn ——> T(n) = O(logn);
3、T(n) = 3 ——> T(n) = O(1);
4、T(n) = 3n^2 + 3n ——> T(n) = O(n^2);
如果n足夠大，他們的時間大小為
O(1) < O(logn) < O(n) < O(n^2)
空間復雜度
在運算的過程中，我們經常需要一些中間數據來輔助我們更好地進行計算，那這些中間數據用什么數據結構來存儲才能提高我們的運算效率呢?
S(n) = O(f(n))
同樣的，他也有幾種隨n增長的趨勢變化：
- 當所占空間與輸入規(guī)模n無關時（只需要固定的存儲空間），其空間復雜度記作
O(1)； - 分配的空間為一個線性的集合（數組等），且集合大小與n成正比，則記作
O(n)； - 分配空間為二維空間（二維數組[][]），且長度與寬度都與n成正比，則記作
O(n^2)； -
遞歸空間，當執(zhí)行遞歸時，系統(tǒng)會分配一塊空間來存儲
方法調用棧，存在兩個動作"入棧"和"出棧"，當我們每次遞歸執(zhí)行函數時，系統(tǒng)都會將函數代碼和參數壓入棧中，而當函數執(zhí)行返回操作時，才會出棧。很明顯，空間復雜度與遞歸深度成正比，即O(n)；
兩者該如何權衡，還是具體看應用場景的，一般來說，大家對程序執(zhí)行的時間要求比較苛刻。
