各種演算法的時間復雜度

❶ C語言 各常見排序法的時間復雜度 急 請簡單說明

選擇排序演算法復雜度是O(n^2)。
插入排序是O(n^2)
快速排序快速排序是不穩定的。最理想情況演算法時間復雜度O(nlog2n)，最壞O(n^2)。
堆排序演算法時間復雜度O(nlogn)。
歸並排序的時間復雜度是O(nlog2n)。

❷ 各種演算法的時間復雜度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

一般時間復雜度到了2 n(指數階)及更大的時間復雜度,這樣的演算法我們基本上不會用了,太不實用了.比如遞歸實現的漢諾塔問題演算法就是O(2 n).

平方階(n^2)的演算法是勉強能用,而nlogn及更小的時間復雜度演算法那就是非常高效的演算法了啊.

空間復雜度
冒泡排序,簡單選擇排序,堆排序,直接插入排序,希爾排序的空間復雜度為O(1),因為需要一個臨時變數來交換元素位置,(另外遍歷序列時自然少不了用一個變數來做索引)

快速排序空間復雜度為logn(因為遞歸調用了) ,歸並排序空間復雜是O(n),需要一個大小為n的臨時數組.

基數排序的空間復雜是O(n),桶排序的空間復雜度不確定

原文： https://blog.csdn.net/weiwenhp/article/details/8622728