23.以下敘述,何者不正確? (A)排序問題是一種NP問題 (B)Bubbl..-阿摩線上測驗
1F 安身立命 國二下 (2016/04/17)
像是排序問題可以用 O(N log N) 複雜度的演算法解決,由於 ,所以排序問題的複雜度低於 O(N^2) ,所以當然屬於「多項式時間」的問題。 同樣的、像是「搜尋、矩陣相乘、計算反矩陣、....」等等常見的問題,幾乎都屬於「多項式時間」的問題 非決定性演算法 (Nondeterministic algorithm) 在電腦領域,非決定性演算法是指那些「針對相同的輸入,每次執行結果可能不同的演算法」,像是「平行的演算法」就會與「執行順序」有關,而「隨機式演算法」則會與「亂數的產生方式」有關。 NP (Nondeterministic Polynomial Time) 問題 如果一個「隨機式演算法」有時只需要「多項式時間」,但有時又需要「指數時間」才能完成,這類的演算法就稱為「非決定性多項式... 查看完整內容 |
2F 澐 高三下 (2018/02/01)
查看完整內容 |
3F 【站僕】摩檸Morning 國三下 (2018/02/06)
原本題目: 23.以下敘述,何者不正確? (A)排序問題是一種NP問題 (B) Bubble Sort的時間效率是0(n2) (C) Merge Sort 的時間效率是 0(n log n) (D) Bubble Sort與Merge Sort的空間效率相同 修改成為 23.以下敘述,何者不正確? (A)排序問題是一種NP問題 (B) Bubble Sort的時間效率是0(n2) (C) Merge Sort 的時間效率是 0(n log n) (D) Bubble Sort與Merge Sort的空間效率相同 |