Q237.
下列之Foo 演算法，哪些描述是正確的？
電腦軟體設計共同科目 · 乙級 · Q237
難易度分析
3 / 5
本題為複選題，要求考生同時分析演算法的功能、時間複雜度以及具體的數值運算結果。由於必須正確判定多個選項的真偽才能得分，且涉及對時間複雜度 O(n) 與 O(log n) 的精確區分，增加了解題的認知難度。
正確答案 (複選)：①, ④
- ① 演算法之功能為計算
:此演算法透過初始化 b = 1，在 while 迴圈中將 b 累乘 a 共 n 次，最終回傳 b，其功能即為計算 a 的 n 次方（aⁿ）。 - ④ while 迴圈的敘述之計算時間為O(n):while 迴圈的條件為 k < n，k 從 0 遞增至 n，共執行 n 次迭代，每次迭代包含加法與乘法兩個常數時間操作，故迴圈整體計算時間為 O(n)。
錯誤選項解析
- ② 演算法之計算時間為O(log n):此演算法的 while 迴圈執行 n 次迭代，每次迭代為常數時間操作，故計算時間為 O(n) 而非 O(log n)；O(log n) 通常出現在每次將問題規模減半的演算法（如二元搜尋）。
- ③ Foo (4, 7)之結果為8192:Foo(4, 7) 計算的是 4⁷ = 4 × 4 × 4 × 4 × 4 × 4 × 4 = 16384，而非 8192（8192 為 2¹³），此選項數值錯誤。
Learning Tip
"此題考點為迴圈次數分析與演算法功能辨識。常見陷阱為混淆 O(n) 與 O(log n)：當迴圈變數每次遞增固定值（如 k ← k + 1）時為 O(n)；只有當變數每次倍增或問題規模減半（如 k ← k * 2）時才為 O(log n)。另外，計算 aⁿ 的樸素方法為 O(n)，若要達到 O(log n) 需使用快速冪演算法（Exponentiation by Squaring）。"
學員答題分佈
①演算法之功能為計算0%
0%②演算法之計算時間為O(log n)0%
③Foo (4, 7)之結果為81920%
④while 迴圈的敘述之計算時間為O(n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
