ziggy-docs

Appearance

分治算法 ​

思想 ​

  • 将一个复杂问题分成两个或多个相同或相似的子问题
  • 再将子问题分成更小的子问题......直到可以直接求解的程度
  • 最后将子问题的解合并构建出原问题的解

步骤 ​

分治算法一般分为三个步骤

  • 分解(Divide):将问题分解为较小规模的同类子问题
  • 解决(Conquer):若子问题规模较小而可以直接解决；否则递归地应用分解步骤
  • 合并(Combine):将子问题的解合并为原问题的解

分治算法的思想主要用于求解递归结构问题,如归并排序、快速排序、二叉搜索树等。它可以将求解复杂问题的时间复杂度大大降低

例题 ​

pow ​

js
function myPow(x, n) {
  if (n === 0)
    return 1
  const pow = Math.abs(n)
  const res = pow % 2 === 0 ? myPow(x * x, pow / 2) : myPow(x * x, (pow - 1) / 2) * x
  return n > 0 ? res : 1 / res
}
function myPow(x, n) {
  if (n === 0)
    return 1
  const pow = Math.abs(n)
  const res = pow % 2 === 0 ? myPow(x * x, pow / 2) : myPow(x * x, (pow - 1) / 2) * x
  return n > 0 ? res : 1 / res
}