快速排序的三種時間復雜度，php快速排序空間復雜度,PHP 算法基礎----時間復雜度和空間復雜度（轉載）

算法復雜度分為時間復雜度和空間復雜度。

其作用：

時間復雜度是指執行算法所需要的計算工作量；

而空間復雜度是指執行這個算法所需要的內存空間。

快速排序的三種時間復雜度？(算法的復雜性體現在運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間(即寄存器)資源，因此復雜度分為時間和空間復雜度)。

簡單來說，時間復雜度指的是語句執行次數，空間復雜度指的是算法所占的存儲空間

時間復雜度

計算時間復雜度的方法：

用常數1代替運行時間中的所有加法常數

php快速排序算法。修改后的運行次數函數中，只保留最高階項

去除最高階項的系數

按數量級遞增排列，常見的時間復雜度有：

常數階O(1),對數階O(log2n),線性階O(n),

線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),…，

數組排序的時間復雜度為nlog2(n)，k次方階O(n^k),指數階O(2^n)。

隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低。

舉個栗子:

sum = n*(n+1)/2; //時間復雜度O(1)

for(int i = 0; i < n; i++){

時間復雜度與空間復雜度，printf("%d ",i);

}

//時間復雜度O(n)

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

基本復雜度？printf("%d ",i);

}

}

//時間復雜度O(n^2)

for(int i = 0; i < n; i++){

php排序、for(int j = i; j < n; j++){

printf("%d ",i);

}

}

//運行次數為(1+n)*n/2

順序查找的時間復雜度？//時間復雜度O(n^2)

int i = 0, n = 100;

while(i < n){

i = i * 2;

}

快速排序的平均時間復雜度為，//設執行次數為x. 2^x = n 即x = log2n

//時間復雜度O(log2n)

最壞時間復雜度和平均時間復雜度

最壞情況下的時間復雜度稱最壞時間復雜度。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。

這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何更長。

歸并排序時間復雜度？平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下，算法的期望運行時間。設每種情況的出現的概率為pi,平均時間復雜度則為sum(pi*f(n))

常用排序算法的時間復雜度

算法

最差時間分析

平均時間復雜度

復雜度。穩定度

空間復雜度冒泡排序

O(n2)

O(n2)

穩定

快速排序的空間復雜度怎么算。O(1)

快速排序

O(n2)

O(n*log2n)

不穩定

O(log2n)~O(n)

選擇排序

O(n2)

O(n2)

穩定

O(1)

二叉樹排序

O(n2)

O(n*log2n)

不穩定

O(n)

插入排序

O(n2)

O(n2)

穩定

O(1)

堆排序

O(n*log2n)

O(n*log2n)

不穩定

O(1)

希爾排序

O

O

不穩定

O(1)

空間復雜度

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。

對于一個算法來說，空間復雜度和時間復雜度往往是相互影響的。當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間；反之，當追求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。

有時我們可以用空間來換取時間以達到目的。

本作品采用《CC 協議》，轉載必須注明作者和本文鏈接