php中冒泡排序的时间复杂度和空间复杂度是什么

小编给大家分享一下php中冒泡排序的时间复杂度和空间复杂度是什么，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

冒泡排序的时间复杂度和空间复杂度

1、代码实现

         $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、计算原理

• 第一轮：将数组的第一个元素和其他所有的元素进行比较，哪个元素更大，就换顺序，从而冒泡出第一大（最大）的元素

• 第一轮：将数组的第二个元素和其他所有的元素进行比较（第一大已经筛选出来不用继续比较了），哪个元素更大，就换顺序，从而冒泡出第二大的元素

• ... 依次类推，冒泡从大到小排序的数组

平均时间复杂度：O(n^2) ；

最优时间复杂度：O(n) ，需要加判断，第一次循环如果一次都没有交换就直接跳出循环

空间复杂度：O(1)，交换元素的时候的临时变量占用的空间

最优空间复杂度：O(1)，排好序，不需要交换位置

3、时间复杂度和空间复杂度

时间复杂度：全程为渐进时间复杂度，估算对处理器的使用效率（描述算法的效率趋势，并不是指算法具体使用的时间，因为不同机器的性能不一致，只是一种效率计算的通用方法）

表示方法：大O符号表示法

复杂度量级：

• 常数阶O(1)

• 线性阶O(n)

• 平方阶O(n²)

• 立方阶O(n³)

• K次方阶O(n^k)

• 指数阶(2^n)

• 对数阶O(logN)

• 线性对数阶O(nlogN)

时间复制类型：

• 最好时间复杂度

• 最坏时间复杂度

• 平均时间复杂度

• 均摊时间复杂度

空间复杂度：全程渐进空间复杂度，估算对计算机内存的使用程度（描述算法占用的存储空间的趋势，不是实际占用空间，同上）

看完了这篇文章，相信你对“php中冒泡排序的时间复杂度和空间复杂度是什么”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！