Q88.
下列敘述何者是正確的？
電腦軟體設計共同科目 · 乙級 · Q88
難易度分析
4 / 5
本題要求考生區分時間複雜度與空間複雜度的獨立性，並能精確運用數學公式分析漸進符號的正確性，且選項中包含容易混淆的數學推導與定義，需具備紮實的理論基礎才能正確判別。
正確答案：③
③ :根據 Stirling 近似公式，log(n!) ≈ n·log n - n + O(log n)，因此 log(n!) 的漸進複雜度為 Θ(n log n)，自然滿足 log n! = O(n log n)，此為正確敘述。
:根據 Stirling 近似公式，log(n!) ≈ n·log n - n + O(log n)，因此 log(n!) 的漸進複雜度為 Θ(n log n)，自然滿足 log n! = O(n log n)，此為正確敘述。錯誤選項解析
- ①
:該式為 Σ⌈log(n/i)⌉ (i=1~n)，其值約等於 log(nⁿ/n!) = n·log n - log(n!)，根據 Stirling 公式 可知 log(n!) ≈ n·log n - n，因此總和為 O(n) 而非 O(n)，實際應為 O(n) 量級，此敘述不正確。 - ②
:5n² + 15n 的最高次項為 n²，其 漸進時間複雜度 應為 O(n²)。雖然 O(n²) 在數學上確實是 O(n³) 的子集合（大 O 表示上界），但在演算法分析中應給出 最緊確的上界 (tight bound)，故此敘述不夠精確。 - ④ 對於一個時間複雜度為O(1)的演算法而言，不管其輸入資料量(Input Size)為何，其所需記憶體大小是固定的:時間複雜度 O(1) 僅表示執行時間為常數，與 空間複雜度 無直接關聯。一個 O(1) 時間的演算法仍可能使用 O(n) 的記憶體空間，兩者需分開討論。
Learning Tip
"本題考 漸進符號 (Asymptotic Notation) 的正確理解。常考陷阱：(1) 大 O 表示上界，但實務上應給出最緊確界；(2) 時間複雜度與空間複雜度是獨立概念，不可混淆；(3) Stirling 公式 log(n!) = Θ(n log n) 是資料結構與演分析中的核心結論，務必熟記。"
學員答題分佈
①0%
0%②0%
0%③0%
0%④對於一個時間複雜度為O(1)的演算法而言，不管其輸入資料量(Input Size)為何，其所需記憶體大小是固定的0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
