前端大厂算法考点须知

什么是时间复杂度？

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

如何计算时间复杂度？

当问题规模随着处理数据的增长时，基本操作要重复执行的次数必定会随着增长，那么我们需要知道执行次数是以什么样的数量级增长的。

接下来我们用大O表示法标识一下常见的时间复杂度量级：

O(1)

常数阶的复杂度，这种复杂度无论数据规模n如何增长，计算时间是不变的。

一个简单的例子：

const add = (a, b) => a + b

不管n如何增长，都不会影响到这个函数的执行时间，因此这个函数的时间复杂度为O(1)。

O(n)

线性复杂度，随着数据规模n的增长，时间复杂度也会随着n线性增长

const indexOf = (arr, target) => {
  let len = arr.length
  while(len--) {
    if (arr[len] === target) {
      return arr[len]
    }
  }
}

O(logn)

对数复杂度，随着问题规模n的增长，计算时间也会随着n对数级数增长。
如数据增大1024倍时，时间只增大32倍，是比线性复杂度还要低的时间复杂度。

典型的例子就是二分查找法。（二分查找只支持已经排好序的数组）

functions binarySearch(arr, target) {
    let max = arr.length - 1
    let min = 0
    while (min <= max) {
        let mid = Math.floor((max + min) / 2)
        if (target < arr[mid]) {
            max = mid - 1
        } else if (target > arr[mid]) {
            min = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。

事实上在实际项目中，O(logn)是一个非常好的时间复杂度，比如当n=100的数据规模时，二分查找只需要7次，线性查找需要100次，这对于计算机而言差距不大，但是当有10亿的数据规模的时候，二分查找依然只需要30次，而线性查找需要惊人的10亿次，O(logn)时间复杂度的算法随着数据规模的增大，它的优势就越明显。

O(n²)

平方级复杂度，典型情况是当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了，代表应用是冒泡排序算法。

冒泡排序

实现原理：
以最终目标为升序排列为例：

1. 比较相邻的两个元素，如果第一个元素小于第二个，则交换位置。
2. 从开始的两个元素开始对比，一直对比到最后，直到最后一个数为最大值。
3. 不断重复以上的步骤，得到最终的结果

// 冒泡排序
function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

冒泡排序增强版

为了提升效率，增加最小值，和最大值，并且正反分别对比一次。减少执行的对比次数，从而达到提高效率的目的。

function bubbleSortEnhancement(arr) {
  let low = 0
  let high = arr.length - 1
  let i
  let temp
  while (low < high) {
    for (i = low; i < high; i++) {
      if (arr[i] > arr[i + 1]) {
        temp = arr[i]
        arr[i] = arr[i + 1]
        arr[i + 1] = temp
      }
    }
    high--

    for (i = high; i > low; i--) {
      if (arr[i] < arr[i - 1]) {
        temp = arr[i]
        arr[i] = arr[i - 1]
        arr[i - 1] = temp
      }
    }
    low++
  }
  return arr
}

O(nlogn)

当数据增大n倍时，执行时间随着增大nlogn倍，这个复杂度高于线性复杂度，低于平方复杂度。归并排序和快速排序就是典型的代表。

快速排序

实现原理：

1. 将要排序的数据分割成独立的两部分
2. 其中一部分的所有数据要比另外一部分的所有数据要小
3. 然后按这两部分数据分别进行快速排序，可以使用递归进行
4. 以此达到整个数据变成有序序列

// 快速排序
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var pivotIndex = Math.floor(arr.length / 2)
  var pivot = arr.splice(pivotIndex, 1)[0]
  var left = []
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}

归并排序

实现原理：

1. 把一个长度为n的数组分为n/2长度的两个子数组
2. 对两个数组分别执行归并排序
3. 最终合并两个数组

function mergeSort(arr) {
  //采用自上而下的递归方法
  var len = arr.length
  if (len < 2) {
    return arr
  }
  var middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  var result = []
  console.time('归并排序耗时')
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  while (left.length) result.push(left.shift())

  while (right.length) result.push(right.shift())
  console.timeEnd('归并排序耗时')
  return result
}