阿摩線上測驗
23.以下敘述，何者不正確?
(A)排序問題是一種NP問題
(B) Bubble Sort的時間效率是0(n2)
(C) Merge Sort 的時間效率是 0(n log n)
(D) Bubble Sort與Merge Sort的空間效率相同
答案：登入後查看
統計： A(28), B(4), C(4), D(31), E(0) #615284
統計： A(28), B(4), C(4), D(31), E(0) #615284
詳解 (共 3 筆)
安身立命
#1313662
像是排序問題可以用 O(N log N) 複雜度的演算法解決，由於 ，所以排序問題的複雜度低於 O(N^2) ，所以當然屬於「多項式時間」的問題。
同樣的、像是「搜尋、矩陣相乘、計算反矩陣、....」等等常見的問題，幾乎都屬於「多項式時間」的問題
非決定性演算法 (Nondeterministic algorithm)
在電腦領域，非決定性演算法是指那些「針對相同的輸入，每次執行結果可能不同的演算法」，像是「平行的演算法」就會與「執行順序」有關，而「隨機式演算法」則會與「亂數的產生方式」有關。
NP (Nondeterministic Polynomial Time) 問題
如果一個「隨機式演算法」有時只需要「多項式時間」，但有時又需要「指數時間」才能完成，這類的演算法就稱為「非決定性多項式時間」(Nondeterministic polynomial time) 演算法。
而那些可以用「非決定性多項式時間演算法」解決的問題，我們就稱為 NP 問題。
當然、有很多問題都屬於 NP 問題。
舉例而言、像是排序問題可以用 O(N log N) 複雜度的演算法解決，由於 ，所以排序問題的複雜度低於 O(N^2) ，所以當然屬於「多項式時間」的問題。
同樣的、像是「搜尋、矩陣相乘、計算反矩陣、....」等等常見的問題，幾乎都屬於「多項式時間」的問題，當然也可以用「決定性多項式時間的演算法」(Deterministic Polynomial Time Algorithm)來解決。
事實上，上述那些明確受制於 的問題，像是「排序、搜尋、矩陣相乘、計算反矩陣、....」等等，都屬於「決定性多項式問題」(Polynomial Time Problem)，簡稱 P 問題。
但是、對於某些問題，我們知道當採用「非決定性演算法」的時候，有時可以很快的傳回解答 (在 之內)，有時卻又要很久才能傳回解答 (需要 的步驟)，但是我們卻沒有把握每次都能多項式時間 內傳回解答。這種問題屬於「非決定性多項式時間」當中較難的一類問題，這類問題是我們特別想要關注的「較難的 NP 問題」。
3
0
