【安身立命】評論

像是排序問題可以用 O(N log N) 複雜度的演算法解決，由於  ，所以排序問題的複雜度低於 O(N^2) ，所以當然屬於「多項式時間」的問題。同樣的、像是「搜尋、矩陣相乘、計算反矩陣、....」等等常見的問題，幾乎都屬於「多項式時間」的問題非決定性演算法 (Nondeterministic algorithm)在電腦領域，非決定性演算法是指那些「針對相同的輸入，每次執行結果可能不同的演算法」，像是「平行的演算法」就會與「執行順序」有關，而「隨機式演算法」則會與「亂數的產生方式」有關。NP (Nondeterministic Polynomial Time) 問題如果一個「隨機式演算法」有時只需要「多項式時間」，但有時又需要「指數時間」才能完成，這類的演算法就稱為「非決定性多項式...

【澐】評論

演算法時間複雜度空間複雜度穩定性類型BestWorstAvg選擇排序法(Selection Sort)Ο(n2)Ο(n2)Ο(n2)Ο(1)不穩定選擇插入排序法(Insertion Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定插入氣泡排序法(Bubble Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定交換謝爾排序法(Shell Sort)Ο(n)Ο(n2)~ Ο(n1.5)Ο(n5/4)Ο(n) + Ο(1)不穩定插入搖晃排序法(Shaker Sort)Ο(n)Ο(n2)Ο(n2)Ο(1)穩定交換快速排序法(Quick Sort)Ο(n log n)Ο(n2)Ο(n log n)Ο(log n)~Ο(n)不穩定交換合併排序法(Merge Sort)Ο(n log n)Ο(n log n)Ο(n log n)Ο(n)穩定合併堆積排序法(Heap Sort)Ο(n log n)Ο(n log n)Ο(n log n)Ο(n) + Ο(1)不穩定選擇基數排序(Radix Sort)Ο(d×(n+r))Ο(d...

【【站僕】摩檸Morning】評論

原本題目: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的空間效率相同