有關演算法，何者為錯誤？
ANP-complete 問題是 NP-hard 問題的子集（subset）
B不能在多項式時間（polynomial-time）內完成的問題即為 NP-complete正確答案
C複雜度 O(n²)>O(nlog(n))>O(n)
D空間複雜度（Space Complexity）指的是使用記憶體的多寡
答案與詳解
逐選項解析
ANP-complete 問題是 NP-hard 問題的子集（subset）✕ 錯誤
此選項敘述正確。NP-complete 問題必須同時滿足屬於 NP 且為 NP-hard，因此 NP-complete 確實是 NP-hard 的子集。因題目要求選出錯誤敘述，故非正確答案。
B不能在多項式時間（polynomial-time）內完成的問題即為 NP-complete✓ 正確
此選項敘述錯誤。NP-complete 問題必須首先屬於 NP 類（即能在多項式時間內驗證解答），且所有 NP 問題皆可多項式時間歸約至該問題。許多無法在多項式時間內解決的問題（如 EXPTIME 完整問題）並不屬於 NP，因此不能直接等同於 NP-complete。符合題目選錯之要求，故為正確答案。
C複雜度 O(n²)>O(nlog(n))>O(n)✕ 錯誤
D空間複雜度（Space Complexity）指的是使用記憶體的多寡✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
