Examly題庫立即開始練習
國中教甄|資訊科技資訊科技112 年第 22 題單選題

若有一個演算法 A 能解決排序問題(Sorting Problem),當演算法 A 解決排序問題時,對最差情況(worse case)所花的時間為 ,對最佳情況(best case)所花的時間為 ,請問以下敘述何者正確?

A演算法 A 的時間複雜度 $T(n)=\Theta(n^{2})$
B演算法 A 的時間複雜度 $T(n)=O(n^{2})$正確答案
C演算法 A 的時間複雜度 $T(n)=\Omega(n^{2})$
D演算法 A 的時間複雜度 $T(n)=\Theta(n)$
答案與詳解
B
正確答案
未特別指明情況時,Big-O 表示涵蓋所有情況的安全上界,而 Big-Theta 要求上下界一致,因最佳情況為線性時間,故僅能選 O(n^2)。

為什麼答案是 B

Big-O 代表上界,表示演算法的執行時間不會超過 n^2 級別。無論是 worst case 的 n^2+n 或 best case 的 3n+1,皆滿足 O(n^2) 的定義,故為最精確且正確的整體描述。

載入中…

資訊科技 相關題目

想練更多資訊科技考古題?

Examly 收錄 38 萬+ 道歷屆題目,每題都有像這樣的精選詳解。免費下載,立即開練。

黑皮