地特三等申論題
108年
[資訊處理] 資料結構
第 三 題
📖 題組：
對下列三個程式片段，請使用 Big-O 符號，分別估計其最長執行時間（worst time）。程式片段中，S 代表一段沒有與 n 相關的迴圈（no n-dependent loops）。
(一) for (int i = 0; i * i < n; i++) （5 分）
S
(二) for (int i = 0; Math.sqrt (i) < n; i++) （5 分）
S
(三) int k = 1; （10 分）
for (int i = 0; i < n; i++)
k *= 2;
for (int i = 0; i < k; i++)
S
對下列三個程式片段，請使用 Big-O 符號，分別估計其最長執行時間（worst time）。程式片段中，S 代表一段沒有與 n 相關的迴圈（no n-dependent loops）。
(一) for (int i = 0; i * i < n; i++) （5 分）
S
(二) for (int i = 0; Math.sqrt (i) < n; i++) （5 分）
S
(三) int k = 1; （10 分）
for (int i = 0; i < n; i++)
k *= 2;
for (int i = 0; i < k; i++)
S
📝 此題為申論題，共 3 小題
小題 (三)
int k = 1; for (int i = 0; i < n; i++) k *= 2; for (int i = 0; i < k; i++) S
思路引導 VIP
首先，將程式片段拆解為兩個獨立循序的迴圈分別分析。先觀察第一個迴圈對變數 k 的影響，推導出 k 最終的數值（表示為 n 的函數）；接著將該 k 值帶入第二個迴圈，計算其執行次數，最後相加取最高階項作為整體的 Big-O 複雜度。
小題 (一)
for (int i = 0; i * i < n; i++) S
思路引導 VIP
判斷時間複雜度的關鍵在於找出迴圈的「終止條件」與迴圈變數的「遞增規律」。本題變數每次線性加 1，但終止條件是變數的平方小於 n，直接解數學不等式即可得到執行次數與輸入規模 n 的關係。
小題 (二)
for (int i = 0; Math.sqrt (i) < n; i++) S
思路引導 VIP
看到迴圈時間複雜度題，首要任務是解出計數器變數 i 與輸入規模 n 之間的不等式終止關係。將終止條件 Math.sqrt(i) < n 兩邊同時平方，即可直接得出 i < n^2，配合 i 每次線性遞增 1 的特性，便能精確推導出迴圈執行的總次數。
時間複雜度分析技巧
💡 依程式結構拆解，追蹤變數規律後取其最高漸近階項。
🔗 程式複雜度分析流程
- 1 模組拆解 — 將程式依據循序或嵌套結構劃分為獨立分析單元。
- 2 變數追蹤 — 推導迴圈控制變數（如 k）隨 n 變化的代數表達式。
- 3 運算加總 — 將各區塊執行次數加總，本題為 O(n) + O(2^n)。
- 4 簡化取階 — 套用 Big-O 定義，取最高階項 O(2^n) 作為最終答案。
↓
↓
↓
🔄 延伸學習：延伸學習：常用複雜度排序 O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
