Examly題庫立即開始練習
普考-資訊處理計算機概要1125單選題

一個演算法具有較低的複雜度(algorithm complexity),下列何者必然成立?

A在不同運算環境中都具有較佳效率
B問題規模趨近無限大時,比其他較高複雜度演算法所需步驟數目較少正確答案
C可以解決NP-hard的問題
D可以提供最佳結果(optimized solution)
答案與詳解
B
正確答案
演算法複雜度是漸近分析,只有在問題規模 n 趨近無限大時,低複雜度才保證步驟數較少。

為什麼答案是 B

Big-O 就是當 n→∞ 時的漸近上界,因此問題規模夠大時,低複雜度演算法所需步驟數必然少於高複雜度者,這正是複雜度分析的定義。

考點:環境無關性考點:漸近分析定義考點:NP-hard考點:效率 vs 最佳解
載入中…

計算機概要 相關題目

想練更多計算機概要考古題?

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

Download on theApp Store即將推出Google Play
黑皮