下列之Bar 演算法，那些描述是正確的？

電腦軟體設計共同科目 · 乙級 · Q259

演算法之功能為計算 a

演算法之計算時間為O(log n)

while 迴圈內的敘述之計算時間為O(1)

Bar(6, 5)之結果為15625

4 / 5

本題採取多選形式，要求對演算法的功能定義、時間複雜度分析以及實際數值運算結果進行綜合判定。由於需完整分析所有選項且包含易混淆的數值陷阱，因此提升了認知負荷與作答難度。

① 演算法之功能為計算 a :此 Bar 演算法為經典的快速冪運算（Exponentiation by Squaring），其功能為計算 a^n（a 的 n 次方），透過將指數不斷除以 2 並對底數進行平方來加速計算。
② 演算法之計算時間為O(log n):由於 while 迴圈每次迭代將指數 n 除以 2（整數除法），因此迴圈執行次數為 log₂n，整體時間複雜度為 O(log n)，遠優於線性相乘的 O(n)。
③ while 迴圈內的敘述之計算時間為O(1):while 迴圈內的敘述包含：奇偶判斷（n % 2）、乘法運算（result * a 與 a * a）、以及整數除法（n / 2），這些皆為常數時間 O(1) 的基本運算。

④ Bar(6, 5)之結果為15625:Bar(6, 5) 計算的是 6⁵ = 7776，而非 15625；15625 實際上是 5⁶ 的結果，此選項將底數與指數顛倒混淆。

"本題核心考點為快速冪演算法的時間複雜度分析與功能辨識。常見陷阱在於混淆 O(log n) 與 O(n) 的差異，以及誤算 Bar(a, n) 的實際數值（注意底數與指數的順序）。實務上此演算法廣泛應用於密碼學中的模冪運算（如 RSA 加密），掌握指數折半的設計思想是解題關鍵。"

①演算法之功能為計算 a

②演算法之計算時間為O(log n)0%

③while 迴圈內的敘述之計算時間為O(1)0%

④Bar(6, 5)之結果為156250%

此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！