名词解释

  • 多项式级 即 n^2 n^3 可以被认为是可控的算法复杂度级别
  • 指数级 x^n 级别 非常恐怖

分治法

分治法是一种极为重要的算法设计思想,他的核心思想就是把大问题分解成一些小问题,最后将结果合并起来。通常来讲,分治法一般都比较适合用递归来描述表达。

分治法的基本步骤

  1. 分 即将大块进行拆分
  2. 治 对每一部分进行处理
  3. 合 将处理完的部分进行重新的整合

几种具有代表性的分治法

归并排序

归并排序就是一种非常典型的分治排序算法,他的原理就是不断的去合并两个排序完成的数组。

function mergeSort(arr){
  if(arr.length === 1){
    return arr
  }
  
  let middleIndex = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0,middleIndex))
  let right = mergeSort(arr.slice(middleIndex,arr.length))
  
  return mergeArray(left,right)
}

function mergeArray(arr1,arr2){
  let start1 = 0,start2 = 0 ,end1=arr1.length -1,end2 = arr2.length - 1
  let res = []
  while (start1 <= end1 && start2 <= end2) {
    arr1[start1] < arr2[start2] ? res.push(arr1[start1++]) : res.push(arr2[start2++])
  }
  while(start1 <= end1){
    res.push(arr1[start1++])
  }
  while(start2 <= end2){
    res.push(arr2[start2++])
  }
  return res
}

T(n) = 2T(n / 2) + O(n)

  1. 分 一分为二
  2. 治 递归的对子数组进行排序
  3. 合 合并两个排序完成的数组

朴素算法

求幂

function pusu(x, n) {
  function _pusu(n) {
    if (n === 1) { return x }

    let half
    let res

    if (n % 2 === 0) {
      half = _pusu(n / 2)
      res = half * half
    } else {
      half = _pusu((n - 1) / 2)
      res = half * half * x
    }

    return res
  }
  return _pusu(n)
}

T(n) = 2T(n/2) + O(1)

  1. 分 将x^n 分为 x^(n/2) * x^(n/2)
  2. 治 递归求x^n的值
  3. 合 half*half

二分查找

这里就不贴出代码了,核心思想就是利用与整个数组的中点值进行比较,不断的缩小其搜索区间。

T(n) = T(n / 2) + O(1)

  1. 分 通过比较大小一分为二
  2. 治 在一个子数组中递归查找
  3. 合 常量级,只需要return即可

fib

fib的递归算法可能算是分治法,但实际上非常的臭,因为一般的分治都是直接减少问题规模的一半,而他则是几乎没有减少,诞生两个相似规模的子问题。

fib的算法复杂度居然是 黄金比例^n 太酷了

分治法分析

首先需要注意的就是分治法的规模是有区别的,有些的1T有些2T乃至3T,这取决去需要分解为多少个子问题。

基本数学公式 n ^ loga(b) n不变 a为分解的子问题数 b 为问题规模的分解量