参考阅读

算法的时间和空间复杂度

什么是算法

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源（空间复杂度）和时间（时间复杂度）却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。

下面我来分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。

反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势****反映的是一个趋势

时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

image.png

1.快速排序

快速排序由于排序效率在同为O(NlogN)*的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用

2. 冒泡排序

算法思想

• 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

算法描述

• 比较相邻的元素，如果前一个比后一个大，交换之。
• 第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
• 接下来第二趟，忽略已经拍好的数字，对于剩下的数字再来一轮
  ......
  动画实现

image

第一轮：

1. 选择 10 和 34， 进行比较， 其中 10 < 34， 二者不需要交换
2. 选择 34 和 21， 进行比较， 其中 34 > 21, 二者需要交换
3. 选择 34 和 47， 进行比较， 其中 34 < 47, 二者需不要交换
4. 选择 47 和 3， 进行比较， 其中 47 > 3, 二者需要交换
5. ...
6. 最后 47 交换到末尾

第二轮：

忽略已经排列好的47, 按照刚刚的逻辑再次排序

...

[图片上传失败...(image-e38d47-1609230829454)]

复杂度

let arr = randomArr(10000, 100)
console.time('bubleSort')  //开始时间
bubleSort(arr)
console.timeEnd('bubleSort')  //结束时间


function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}

function bubleSort(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length - i; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
    }
  }
}

1w长度数组发现平均时间: image.png

以下是10-10万数组长度排序所花时间

image.png

发时间复杂度: [图片上传失败...(image-c3282c-1609230829454)]

空间复杂度: [图片上传失败...(image-39bce5-1609230829454)]

稳定性：稳定

代码实现（JavaScript）

image.png

function bubleSort(arr) {
  for(let i = 0; i < arr.length /*i代表轮数*/; i++) {
    for(let j = 0; j < arr.length - i /*j代表当前轮选中的元素下标*/; j++) {
      if(arr[j] > arr[j+1]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
      }
      //console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
bubleSort(arr)
console.log(arr)

3. 插入排序

代码实现（JavaScript）

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = 0; j < i; j++) {
      if(arr[i] < arr[j]) {
        arr.splice(j, 0, arr[i])
        arr.splice(i+1, 1)
        break
      }
      console.log(arr)
    }
  }
}

var arr = [10, 34, 21, 47, 3, 28]
insertionSort(arr)
console.log(arr)

复杂度

时间复杂度为 O(n^2) ，和上面的测试基本一致。