高考申論題
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 小題
小題 (一)
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
面對雙層巢狀迴圈的時間複雜度計算，應先由外向內（或由內向外）分別評估各層迴圈的執行次數。外層變數呈指數倍增，屬對數時間級別；內層為固定次數的線性遞增，屬線性時間級別。兩者彼此獨立，相乘即為總時間複雜度。
小題 (四)
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 表示法。
Big-O 時間複雜度分析
💡 透過分析迴圈次數與終止條件，判斷程式執行時間級數。
- 分析終止條件：將變數變動規律代入不等式，求出執行次數 k。
- 判定常數時間：S 與 n 無關時視為 $O(1)$，不影響量級。
- 區分增長級數：精確判讀變數之線性、平方、對數或指數成長。
