教甄◆電腦科專業題庫下載題庫

像是排序問題可以用 O(N log N) 複雜度的演算法解決，由於  ，所以排序問題的複雜度低於 O(N^2) ，所以當然屬於「多項式時間」的問題。
同樣的、像是「搜尋、矩陣相乘、計算反矩陣、....」等等常見的問題，幾乎都屬於「多項式時間」的問題

非決定性演算法 (Nondeterministic algorithm)
在電腦領域，非決定性演算法是指那些「針對相同的輸入，每次執行結果可能不同的演算法」，像是「平行的演算法」就會與「執行順序」有關，而「隨機式演算法」則會與「亂數的產生方式」有關。
NP (Nondeterministic Polynomial Time) 問題
如果一個「隨機式演算法」有時只需要「多項式時間」，但有時又需要「指數時間」才能完成，這類的演算法就稱為「非決定性多項式...
查看完整內容

演算法時間複雜度空間複雜度穩定性類型BestWorstAvg選擇排序法(Selection Sort)Ο(n²)Ο(n²)Ο(n²)Ο(1)不穩定選擇插入排序法(Insertion Sort)Ο(n)Ο(n²)Ο(n²)Ο(1)穩定插入氣泡排序法(Bubble Sort)Ο(n)Ο(n²)Ο(n²)Ο(1)穩定交換謝爾排序法(Shell Sort)Ο(n)Ο(n²)~ Ο(n^1.5)Ο(n^5/4)Ο(n) + Ο(1)不穩定插入搖晃排序法(Shaker Sort)Ο(n)Ο(n²)Ο(n²)Ο(1)穩定交換快速排序法(Quick Sort)Ο(n log n)Ο(n²)Ο(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))Ο(...
查看完整內容

演算法	時間複雜度			空間複雜度	穩定性	類型
Best	Worst	Avg
選擇排序法(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×(n+r))	Ο(d×(n+r))	Ο(n×r)	穩定	分配