php中冒泡排序的時(shí)間復(fù)雜度和空間復(fù)雜度是什么

小編給大家分享一下php中冒泡排序的時(shí)間復(fù)雜度和空間復(fù)雜度是什么，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

冒泡排序的時(shí)間復(fù)雜度和空間復(fù)雜度

1、代碼實(shí)現(xiàn)

         $arr = [2, 4, 1, 5, 3, 6];
         for ($i = 0; $i < (count($arr)); $i++) {
             for ($j = $i + 1; $j < (count($arr)); $j++) {
                 if ($arr[$i] <= $arr[$j]) {
                     $temp = $arr[$i];
                     $arr[$i] = $arr[$j];
                     $arr[$j] = $temp;
                 }
             }
         }
     result : [6,5,4,3,2,1]

2、計(jì)算原理

• 第一輪：將數(shù)組的第一個(gè)元素和其他所有的元素進(jìn)行比較，哪個(gè)元素更大，就換順序，從而冒泡出第一大（最大）的元素

• 第一輪：將數(shù)組的第二個(gè)元素和其他所有的元素進(jìn)行比較（第一大已經(jīng)篩選出來不用繼續(xù)比較了），哪個(gè)元素更大，就換順序，從而冒泡出第二大的元素

• ... 依次類推，冒泡從大到小排序的數(shù)組

平均時(shí)間復(fù)雜度：O(n^2) ；

最優(yōu)時(shí)間復(fù)雜度：O(n) ，需要加判斷，第一次循環(huán)如果一次都沒有交換就直接跳出循環(huán)

空間復(fù)雜度：O(1)，交換元素的時(shí)候的臨時(shí)變量占用的空間

最優(yōu)空間復(fù)雜度：O(1)，排好序，不需要交換位置

3、時(shí)間復(fù)雜度和空間復(fù)雜度

時(shí)間復(fù)雜度：全程為漸進(jìn)時(shí)間復(fù)雜度，估算對(duì)處理器的使用效率（描述算法的效率趨勢，并不是指算法具體使用的時(shí)間，因?yàn)椴煌瑱C(jī)器的性能不一致，只是一種效率計(jì)算的通用方法）

表示方法：大O符號(hào)表示法

復(fù)雜度量級(jí)：

• 常數(shù)階O(1)

• 線性階O(n)

• 平方階O(n2)

• 立方階O(n3)

• K次方階O(n^k)

• 指數(shù)階(2^n)

• 對(duì)數(shù)階O(logN)

• 線性對(duì)數(shù)階O(nlogN)

時(shí)間復(fù)制類型：

• 最好時(shí)間復(fù)雜度

• 最壞時(shí)間復(fù)雜度

• 平均時(shí)間復(fù)雜度

• 均攤時(shí)間復(fù)雜度

空間復(fù)雜度：全程漸進(jìn)空間復(fù)雜度，估算對(duì)計(jì)算機(jī)內(nèi)存的使用程度（描述算法占用的存儲(chǔ)空間的趨勢，不是實(shí)際占用空間，同上）

看完了這篇文章，相信你對(duì)“php中冒泡排序的時(shí)間復(fù)雜度和空間復(fù)雜度是什么”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！