高考申論題
105年
[資訊處理] 資料結構
第 四 題
📖 題組：
五、對下列程式片段，請用 Big-O 符號（Big-O notation），分別估計最長執行時間（worst time）。注意：S 中沒有與 n 相關的迴圈（n-dependent loops）。（每小題 5 分，共 20 分）
(一) for (int i = 0; i * i < n; i++) S
(二) for (int i = 1; i < n+1; i*=2) S
(三) for (int i = 1; i < n+1; i*=2)
for (int j = 0; j < n; j++) S
(四) k=1; for (int i=0; i<n; i++)
{k*=3; for (int j=0; j<k; j++) S}
五、對下列程式片段，請用 Big-O 符號（Big-O notation），分別估計最長執行時間（worst time）。注意：S 中沒有與 n 相關的迴圈（n-dependent loops）。（每小題 5 分，共 20 分）
(一) for (int i = 0; i * i < n; i++) S
(二) for (int i = 1; i < n+1; i*=2) S
(三) for (int i = 1; i < n+1; i*=2)
for (int j = 0; j < n; j++) S
(四) k=1; for (int i=0; i<n; i++)
{k*=3; for (int j=0; j<k; j++) S}
📝 此題為申論題，共 4 小題
小題 (四)
k=1; for (int i=0; i<n; i++)
{k*=3; for (int j=0; j<k; j++) S}
{k*=3; for (int j=0; j<k; j++) S}
思路引導 VIP
觀察內外層迴圈的相依關係，將變數 k 隨著外層迴圈 i 增加的變化規律列出，並計算內層迴圈執行次數的總和。利用等比級數公式求和後，即可得出最長執行時間的 Big-O 表示法。
小題 (一)
for (int i = 0; i * i < n; i++) S
思路引導 VIP
分析這類迴圈的時間複雜度，關鍵在於找出迴圈變數的「初始值」、「遞增模式」與「終止條件」。看到條件 i * i < n 且每次 i++，應推導 i 的平方與 n 的不等式關係，進而解出迴圈執行的總次數。
小題 (二)
for (int i = 1; i < n+1; i*=2) S
思路引導 VIP
看到迴圈變數的更新方式為乘法（i*=2），應立刻聯想到指數增長與對數關係。藉由列出每次疊代 i 的數值變化（1, 2, 4..., 2^k），並與終止條件（n+1）建立不等式，即可精準推導出執行次數為對數級別。
小題 (三)
for (int i = 1; i < n+1; i*=2)
for (int j = 0; j < n; j++) S
for (int j = 0; j < n; j++) S
思路引導 VIP
面對雙層巢狀迴圈的時間複雜度計算，應先由外向內（或由內向外）分別評估各層迴圈的執行次數。外層變數呈指數倍增，屬對數時間級別；內層為固定次數的線性遞增，屬線性時間級別。兩者彼此獨立，相乘即為總時間複雜度。
Big-O 複雜度分析
💡 追蹤迴圈變數變化規律，並利用級數公式計算總執行次數。
🔗 複雜度分析推導流程
- 1 變數規律 — 觀察知 i=0,1,2..n-1 時，k 為 3,9..3^n
- 2 級數加總 — 列出總次數為 3¹ + 3² + ... + 3ⁿ 之和
- 3 公式求解 — 套用等比級數公式求得閉合式為 1.5(3ⁿ-1)
- 4 漸進簡化 — 忽略係數與常數，最終結果為 O(3ⁿ)
↓
↓
↓
🔄 延伸學習：延伸學習：若變數以 i/=2 變化，則需考量對數級數 O(log n)。
