資料結構與算法的誕生是讓計算機「執行的更快」、「更省空間」的。
2、用什麼來評判資料結構與算法的好壞？
從「執行時間」和「占用空間」兩個方面來評判資料結構與算法的好壞。
3、什麼是複雜度？
用「時間複雜度」和「空間複雜度」來描述性能問題，兩者統稱為複雜度。
4、複雜度描述了什麼？
複雜度描述的是算法執行時間（或占用空間）與資料規模的增長關系。
1、和性能分析相比有什麼優點？
輔助度分析有不依賴執行環境、成本低、效率高、易操作、指導性強的特點。
2、為什麼要複雜度分析？
1、什麼方法可以進行複雜度分析？
方法：「大 O 表示法」
2、什麼是大 O 表示法？
算法的「執行時間」與每行代碼的「執行次數」成正比【T(n) = O(f(n)) 】=》其中T(n)表示算法執行總時間，f(n)表示每行代碼執行總次數，而n往往表示資料的規模。
3、大 O 表示法的特點？
由于時間複雜度描述的是算法執行時間與資料規模的增長變化趨勢，常量階、低階以及系數實際上對這種增長趨勢不産決定性影響，是以在做時間複雜度分析時忽略這些項。
4、複雜度分析法則
- [單段代碼看頻率]：看代碼片段中「循環代碼」的時間複雜度。
- [多段代碼看最大]：如果多個 for 循環，看「嵌套循環最多」的那段代碼的時間複雜度。
- [嵌套代碼求乘積]：循環、遞歸代碼，将内外嵌套代碼求乘積去時間複雜度。
- [多個規模求加法]: 法有兩個參數控制兩個循環的次數，那麼這時就取二者複雜度相加。
------------------❤------------------
時間複雜度
1、什麼是複雜度？
所有代碼的「執行時間 T(n)」 與每行代碼的「執行次數n」 成正比【T(n) = O(f(n)) 】。
2、分析的三個方法
■ 最多法則
忽略掉公式中的常量、低階、系數，取最大循環次數就可以了，也就是循環次數最多的那行代碼。
Example
1// 求n個數字之和
2int xiaolu(int n) {
3 int sum = 0;
4 for (int i = 1; i <= n; ++i) {
5 sum = sum + i;
6 }
7 return sum;
8 }
分析
-------------------------------------------
第二行是一行代碼，也就是常量級别，與 n 沒有關系，可以忽略，四、五行代碼是我們重點分析對象，與 n 有關，時間複雜度就是反映執行時間和 n 資料規模的關系。求 n 個資料之和需要執行 n 次。是以時間複雜度為 O(n)。
■ 加法法則
總複雜度等于循環次數最多的那段複雜度。
1int xiaolu(int n) {
2 int sum = 0;
3 //循環一
4 for (int i = 1; i <= 100; j++) {
5 sum = sum + i;
6 }
7 //循環二
8 for (int j = 1; j <= n; j++) {
9 sum = sum + i;
10 }
11 }
上邊有兩個循環，一個循環 100 次，另一個循環 n 次，我們選擇循環次數最多的那一個且和「資料規模 n 」相關的循環。由上可知，我們很容易選出循環二，即和資料規模 n 有關，循環次數最多，循環次數最多的那段代碼時間複雜度就代表總體的時間複雜度，為 O(n) ;
■ 乘法法則
當我們遇到嵌套的 for 循環的時候，怎麼計算時間複雜度呢？那就是内外循環的乘積。
1 for (int j = 1; j <= n; j++) {
2 for(int i = 1; i <= n; i++)
3 sum = sum + i;
4 }
外循環一次，内就循環 n 次，那麼外循環 n 次，内就循環 n*n 次。是以時間複雜為 O(n²)。
空間複雜度
1、什麼是空間複雜度？
表示算法的「存儲空間」與「資料規模」之間的增長關系
1int xiaolu(int n) {
2 int sum = 0;
3 //循環一
4 for (int i = 1; i <= 100; j++) {
5 sum = sum + i;
6 }
7 //循環二
8 for (int j = 1; j <= n; j++) {
9 sum = sum + i;
10 }
11 }
在所有代碼中，我們很容易尋找到存儲空間相關的代碼，就是第二行，申請了一個 n 大小的存儲空間，是以空間複雜度為 O(n)。
2、最常見的空間複雜度
O(1)、O(n)、O(n²)。
■ O(1)
常量級的時間複雜度表示方法，無論是一行代碼，還是多行，隻要是常量級的就用 O(1) 表示。
1int i = 1;
2int j = 2;
3int sum = i + j;
因為這三行代碼，也就是常量級别的代碼不随 n 資料規模的改變而改變。（循環、遞歸除外）
■ O(logn) | O(nlogn)
「對數階時間複雜度」，最難分析的一種時間複雜度。
要求這段代碼的時間複雜度就求這段代碼執行了多少次，看下圖具體分析。
補充
不管是以 2 為底、以 3 為底，還是以 10 為底，可以把所有對數階的時間複雜度都記為 O(logn)，因為對數之間可以轉換的，參照高中課本。
■ O(m+n) | O(m*n)
參照上邊講到的加法和乘法法則。
1、最好、最壞時間複雜度
所謂的最好、最壞時間複雜度分别對應代碼最好的情況和最壞的情況下的執行。
分析：
1、最好情況就是數組的第一個就是我們要查找的資料，上邊代碼之執行一遍就可以，這種情況下的時間複雜度為最好時間複雜度，為 O(1)。
2、最壞的情況就是數組的最後一個才是我們要查找的資料，需要循環周遊 n 遍數組，也就對應最壞的時間複雜度為 O(n) 。
2、平均時間複雜度
平均時間複雜度需要借助機率論的知識去分析，也就是我們機率論中所說的權重平均值，也叫做期望值。
比如上方的例子，假設我們查找的資料在數組中的機率為 1/2；出現在數組中的機率為 n/1,根據下邊的公式就可以算出出現的機率為 1/2n 。
然後我們再把每種情況考慮進去，就可以計算出平均時間複雜度。
3、均攤時間複雜度
■什麼是均攤時間複雜度？
比如我們每 n 次插入資料的時間複雜度為 O(1)，就會有一次插入資料的時間複雜度為 O(n)，我們将這一次的時間複雜度平均到 n 次插入資料上，時間複雜度還是 O(1)。
■ 攤還分析
■ 适用場景
一般應用于某一資料結構，連續操作時間複雜度比較低，但是個别情況時間複雜度特别高，我們将特别高的這一次進行均攤到較低的操作上。
■ 幾種複雜度性能對比
各個時間複雜度的性能