名词解释

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

分治法

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

分治法的基本步骤

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

几种具有代表性的分治法

归并排序

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


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)

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

朴素算法

求幂

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)

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

二分查找

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

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

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

fib

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

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

分治法分析

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

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

算法导论笔记二分治法

TOC