問題詳情

22. 若有一個演算法 A 能解決排序問題（Sorting Problem），當演算法 A 解決排序問題時，對最差情況（worse case）所花的時間為n2+n，對最佳情況（best case）所花的時間為 3n+1，請問以下敘述何者正確？
(A)演算法 A 的時間複雜度 T(n) =Θ(n2)
(B)演算法 A 的時間複雜度 T(n) =O(n2)
(C)演算法 A 的時間複雜度 T(n) =Ω(n2)
(D)演算法 A 的時間複雜度 T(n) =Θ(n)

參考答案

答案：B
難度：計算中-1
書單：沒有書單，新增

用户評論

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】根據演算法 A 在最差情況下的時間為 n^2 + n 和最佳情況下的時間為 3n + 1，我們可以得出以下結論：最差情況下的時間複雜度表示演算法 A 在最壞情況下執行的時間量級，可表示為 O(n^2)。最佳情況下的時間複雜度表示演算法 A 在最好情況下執行的時間量級，可表示為 O(n)。根據以上結論，敘述 (B) 演算法 A 的時間複雜度 T(n) = O(n^2) 是正確的。

【用戶】不叫賭俠的陳小刀

【年級】高三下

【評論內容】根據演算法 A 在最差情況下的時間為 n^2 + n 和最佳情況下的時間為 3n + 1，我們可以得出以下結論：最差情況下的時間複雜度表示演算法 A 在最壞情況下執行的時間量級，可表示為 O(n^2)。最佳情況下的時間複雜度表示演算法 A 在最好情況下執行的時間量級，可表示為 O(n)。根據以上結論，敘述 (B) 演算法 A 的時間複雜度 T(n) = O(n^2) 是正確的。