前言

由于先前筆者花費約一周時間將王道《數據結構》知識點大致過了一遍，圈畫下來疑難知識點，有了大致的知識框架，現在的任務就是將知識點逐個理解透徹，并將leetcode刷題與課后刷題相結合。因此此后的過程中，整理的筆記不僅包含課本知識點，還包含經典課后題講解（主要是筆者認為重要的）以及leetcode代碼（用于深入理解重要知識點）。綜上，復習思路為：大致過一遍知識點有個系統框架->寫代碼深入理解->刷題適應考試模式

經復習，我將本書大致分為四部分——第一章：緒論（主要是算法效率的度量），第二章+第三章+第四章：線性結構（包括數組、鏈表、棧、隊列以及串），第五章+第六章：非線性結構（包括樹、圖），第七章+第八章：實際應用（包括順序查找、樹形查找、散列查找以及各種排序算法）。

本篇文章為第一部分，除了一些零散的概念性知識，只有一個較為重要的考點——時間復雜度分析。記住結論即可，有興趣的同學可以自行推理（本來是想寫一下的，但是太費時間了，而且估計看的人不多，所以自行推理吧）

時間復雜度分析

我們將循環分為兩種類型——等差遞增和等比遞增（遞減可以轉化為遞增）。常見形式如：

• 等差遞增：for(int i=0;i<n;i++)
• 等比遞增：for(int i=1;i<n;i*=2)

為了找出一般規律，我們接下來探究等差遞增和等比遞增的一般形式：

• 等差遞增：for(int i=a₀;i<n;i+=d)。其中a₀為首項，d為等差
• 等比遞增：for(int i=a₀;i<n;i*=q)。其中a₀為首項，q為等比

一、單層for循環

類型	時間復雜度
等差for(int i=a~0~;i< n;i+=d)	O(n)
等比for(int i=a~0~;i< n;i*=q)	O(logn)

推導過程：
（假設運行次數為t，即最后一次運行i=a_t）
1.對于等差遞增，有n-d<=a_t<n，即n-d<=a₀+t * d<n，推導出(n-d-a₀)/d<=t<(n-a₀)/d，忽略常數，有時間復雜度為O(n)
2.對于等比遞增，有n/q<=a_t<n，即n/q<=a₀ * q^t<n，推導出log_q(n/(q * a₀))<=t<log_q(n/a₀)，經過換底公式后忽略常數，有時間復雜度為O(logn)

二、雙層for循環
首先將雙層for循環分為兩種類型：

• 上下變量無關：上層遞增變量與下層遞增變量沒有直接關系。如：
  for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
• 上下變量有關：下層遞增變量依賴于上層遞增變量。如：
  for(int i=0;i<n;i++)
for(int j=0;j<i;j++)//j的初始值為i

  同時我們將遞增類型分為兩種類型：
• 加法（等差遞增）：for(int i=a₀;i<n;i+=d)。其中a₀為首項，d為等差
• 乘法（等比遞增）：for(int i=a₀;i<n;i*=q)。其中a₀為首項，q為等比

假設兩層for循環的判斷條件都是n（即i<n、j<n）：

上下變量無關

第一層for循環	第二層for循環	時間復雜度
乘法	乘法	O(log2n)
乘法	加法	O(nlogn)
加法	乘法	O(nlogn)
加法	加法	O(n2)

上下變量有關

第一層for循環	第二層for循環	時間復雜度
乘法	乘法	O(log2n)
乘法	加法	O(n)
加法	乘法	O(nlogn)
加法	加法	O(n2)

僅有先乘后加的時候有區別，前者為O(nlogn)后者為O(n)——參見2022統考真題，其中便考察了這個知識點

注意：對于上下變量有關，第一層為加法，第二層為乘法的時候，最終的時間復雜度為O(logn!)，根據斯特林公式，n!≈√(2nπ)(n/e)ⁿ，取對數后化簡為nlogn

至于上下for循環參數不一致，在此也不再討論（出題概率較低）