算法思想

分治运褪，分而治之仇奶，將原問題劃分成 n 個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題，這些規(guī)模小的問題與原問題是同質(zhì)的驾窟，本質(zhì)上還是同一個(gè)問題庆猫，遞歸解決這些子問題，然后合并其結(jié)果纫普，就能得到原問題的解阅悍。（PS：當(dāng)然，遞歸不是必須的）

空間換時(shí)間昨稼，來實(shí)現(xiàn)算法時(shí)間復(fù)雜度的優(yōu)化

【分治算法】是很多高效算法的基礎(chǔ)节视，諸如快速排序、歸并排序假栓、傅立葉變換寻行、二分搜索

特征

• 原問題的規(guī)模縮小到一定的程度就很容易解決
  -- 絕大多數(shù)問題都可以滿足匾荆，因?yàn)閱栴}的計(jì)算復(fù)雜性通常都是隨著問題規(guī)模的增加而增加
• 原問題可以分解為若干個(gè)規(guī)模較小的相同問題拌蜘，即該問題具有【最優(yōu)子結(jié)構(gòu)性質(zhì)】
  -- 應(yīng)用分治法的前提杆烁，大多數(shù)問題也可以滿足，它反映了遞歸思想的應(yīng)用
• 分解出的子問題的解可以合并為該問題的解
  -- 能否利用分治法的關(guān)鍵特征简卧。如果只具備第一兔魂、第二特征，而不具備第三特征举娩，則可以考慮動(dòng)態(tài)規(guī)劃或貪心算法
• 分解出的各個(gè)子問題相互獨(dú)立析校，即【子問題之間不包括公共的子問題】
  -- 涉及分治算法的效率，如果各個(gè)子問題不是相互獨(dú)立的铜涉，分治算法要做很多不必需要的工作智玻，重復(fù)地解決公共子問題，此時(shí)采用動(dòng)態(tài)規(guī)劃會(huì)比較好

前三個(gè)特征是使用分治法的關(guān)鍵芙代，而特征4 涉及到分治法的效率問題吊奢。如果不符合3、4特征纹烹，可以嘗試使用動(dòng)態(tài)規(guī)劃或胎心算法來解決页滚。

【動(dòng)態(tài)規(guī)劃】是一種特殊的分治，貪心算法是一種特殊的動(dòng)態(tài)規(guī)劃

適用范圍：

• 分治算法：最優(yōu)子結(jié)構(gòu)
• 動(dòng)態(tài)規(guī)劃：最優(yōu)子結(jié)構(gòu)滔韵、重疊子問題
• 貪心算法：最優(yōu)子結(jié)構(gòu)逻谦、重疊子問題、貪心選擇性質(zhì)

分支模式在每一層上都有三個(gè)步驟：

1. 分解陪蜻，將原問題分解成一系列與原問題同質(zhì)的子問題
2. 解決，遞歸解決各個(gè)子問題贱鼻，若子問題足夠小宴卖，則直接求解
3. 合并，將子問題的結(jié)果合并成原問題的解

舉個(gè)例子

有一個(gè)很經(jīng)典的問題：有100枚硬幣邻悬，其中有1枚略輕一些的假幣症昏，如果用天平秤，請問至少稱幾次一定能找到這枚假幣父丰？

• 如果用傳統(tǒng)的逐枚比較法肝谭，顯然至少需要比較50次
  比較第 i 個(gè)與第 i+1 個(gè)的重量，若相等蛾扇，則i++攘烛，繼續(xù)比較，直到重量不相等镀首，并輸出較輕的硬幣編號(hào)坟漱。

• 采用分治算法

  1. 將100枚硬幣分成3份：33、33更哄、34
  2. 稱重 1芋齿、2 份腥寇，若天枰平衡，則假幣必在另外 34 枚中觅捆；若不平衡赦役，則在較輕的那份 33 枚中
  3. 再將 34 枚分成3份：11、11栅炒、12（或?qū)?33 枚分成 11扩劝、11、11）
  4. 稱重兩組 11 枚的硬幣职辅，若平衡棒呛，則假幣在 12 枚里（或第三份 11 枚）；若不平衡域携，則在較輕的那份 11 枚中
  5. 將 12 枚分成3份：4簇秒、4、4（或?qū)?11 枚分成 4秀鞭、4趋观、3），稱重方法同上
  6. 將 4 枚分成 3 份：1锋边、1皱坛、2，稱重1/1豆巨，若平衡剩辟，則稱重剩下的 2 枚，較輕的 1 枚是假幣往扔；若不平衡贩猎，較輕的 1 枚是假幣。（或?qū)?3 枚分成1萍膛、1吭服、1，稱重1/1蝗罗，若平衡艇棕，則剩下的 1 枚是假幣；若不平衡串塑，則較輕的 1 枚是假幣）

  綜上所述沼琉，最多只需要 5 次就能解決這個(gè)問題！

通過觀察 1-2拟赊、3-4刺桃、5-6 發(fā)現(xiàn)，除了硬幣數(shù)量變化了其他步驟完全一樣吸祟，即 這是一個(gè)子問題的分解過程瑟慈，100-33-11-3桃移，將一個(gè)大問題分解成了容易解決的小問題，且 這些小問題相互獨(dú)立葛碧，每一個(gè) 33 枚硬幣和其他硬幣互不影響借杰。
實(shí)際上類似于數(shù)學(xué)歸納法，先找到最小問題規(guī)模的求解方程进泼，然后考慮隨著問題規(guī)模增大時(shí)的求解方程蔗衡，然后根據(jù)方程式設(shè)計(jì)遞歸程序（當(dāng)然，遞歸不是必須的）乳绕，自頂而下的解決問題绞惦。

歸并排序

歸并排序是【分治算法】的典型應(yīng)用：多次分解數(shù)列，直至子數(shù)列中只有一個(gè)元素（【分】）洋措。然后對子數(shù)列排序济蝉，合并相鄰的有序子數(shù)列，最終形成一個(gè)完整的有序數(shù)列（【治】）菠发。

• 【分】階段：遞歸拆分子序列的過程王滤，遞歸深度為 log2n

歸并排序的分治算法.png

• 【合】階段：將兩個(gè)已經(jīng)有序的、相鄰的子序列合并成一個(gè)有序的序列滓鸠，效率可以達(dá)到 O(n)
  以最后一次合并為例：[4,5,7,8]雁乡、[1,2,3,6]

合并.png

• JavaScript 版的實(shí)現(xiàn)

  function sort(arr, i, j) {
      // 直到拆分成只有一個(gè)元素的子序列
      if(i >= j) return
      // 取中間值，分區(qū)
      let mid = Math.floor((i + j) / 2)
      // 1. 拆分左側(cè)一半
      sort(arr, i, mid)
      // 2. 拆分右側(cè)一半
      sort(arr, mid+1, j)
      // 比較, 合并左側(cè)和右側(cè)的結(jié)果
      merge(arr, i, mid, j)
  }
  function merge(arr, left, mid, last) {
      // 一個(gè)臨時(shí)數(shù)組 及其角標(biāo)指針, 存儲(chǔ)排序后的元素糜俗。即：歸并排序 需要申請額外的空間
      let temp = [], k = 0
      // 左側(cè)的起始角標(biāo) i, 右側(cè)的起始角標(biāo) j
      let i = left, j = mid + 1
      while(i <= mid && j <= last) {
          // 左側(cè)和右側(cè)都是有序的, 一次比較踱稍，把較小的先放進(jìn)臨時(shí)數(shù)組
          // 即：相等的元素不會(huì)交換順序，故歸并排序是穩(wěn)定的
          if(arr[i] < arr[j]) {
              temp[k++] = arr[i++]
          } else {
              temp[k++] = arr[j++]
          }
      }
      // 左側(cè)子序列 和 右側(cè)子序列 的長度不一定是相等的吩跋，但都是有序的寞射，
      // 所以多出來的可以直接放進(jìn)臨時(shí)數(shù)組中
      while(i <= mid) {
          temp[k++] = arr[i++]
      }
      while(j <= last) {
          temp[k++] = arr[j++]
      }
      // 把排好序的數(shù)組temp, 添加進(jìn)原數(shù)組中
      for(let n = 0; n < k; n++) {
          arr[left+n] = temp[n]
      }
  }
  let arr = [53, 16, 88, 79, 93, 19, 47, 20]
  //          0   1   2   3   4   5   6  7
  let i = 0, j = arr.length - 1
  sort(arr, i, j)  // [16, 19, 20, 47, 53, 79, 88, 93]
  

【歸并排序】的效率是比較高的，設(shè)數(shù)列長為N锌钮，將數(shù)列分開成小數(shù)列一共要 logN 步，每步都是一個(gè)合并有序數(shù)列的過程引矩，時(shí)間復(fù)雜度可以記為O(N)梁丘，故一共為 O(N*logN)。
因?yàn)椤練w并排序】每次都是在 相鄰 的數(shù)據(jù)中進(jìn)行操作旺韭，所以【歸并排序】在 O(N*logN) 的幾種排序方法（快速排序氛谜，歸并排序，希爾排序区端，堆排序）也是效率比較高的值漫。

快速排序

【快速排序】也是采用【分治算法】實(shí)現(xiàn)的，是對【冒泡算法】的改進(jìn)织盼。與【歸并排序】不同的是杨何，它需要從數(shù)列中挑出一個(gè)元素作為 基準(zhǔn)酱塔。

• 【分區(qū)】操作： 所有元素比 基準(zhǔn) 小的擺放在 基準(zhǔn) 前面，比 基準(zhǔn)值 大的擺在 基準(zhǔn) 的后面（相同的數(shù)可以到任一邊）危虱。在這個(gè)分區(qū)退出之后羊娃，基準(zhǔn)值 就處于數(shù)列的中間位置。
• 遞歸地重復(fù)【分區(qū)操作】埃跷，直到分區(qū)內(nèi)只有一個(gè)元素蕊玷。

【快速排序】的難點(diǎn)在于 如何選取【基準(zhǔn)點(diǎn)】，并按照【基準(zhǔn)點(diǎn)】排序?
為了簡單起見弥雹，以第一個(gè)元素作為 基準(zhǔn)值

• 填坑法
  思路：

  1. i=begin, j=last垃帅，將基準(zhǔn)挖出，形成第一個(gè)坑arr[i]
  2. 從右向左（j--）找比基準(zhǔn)值小的數(shù)剪勿，填入arr[i]的坑中贸诚，并把基準(zhǔn)值填入arr[j]
  3. 從左向右（i++）找比基準(zhǔn)值大的數(shù)，填入arr[j]的坑中窗宦，并把基準(zhǔn)值填入arr[i]
  4. 重復(fù)步驟2-3赦颇，直至i >= j，則第一個(gè)分區(qū)完成赴涵，基準(zhǔn)值左側(cè)是比基準(zhǔn)小的數(shù)媒怯，基準(zhǔn)值右側(cè)是比基準(zhǔn)大的數(shù)，分別對左分區(qū)和有分區(qū)進(jìn)行排序髓窜。

  function sort(arr, begin, last) {
      if(begin >= last) {
          return
      }
      let i = begin, j = last, mid
      let base = arr[i]
      while(true) {
          // j 從后向前找比 base 小的數(shù), 并放到基準(zhǔn)值左側(cè)
          while(i !== j) {
              if(arr[j] < base) {
                  // 找到了, 與基準(zhǔn)值交換位置
                  arr[i] = arr[j]
                  arr[j] = base  // j 指向基準(zhǔn)值
                  break
              } else {
                  // 沒找到, 則向后移動(dòng)角標(biāo), 繼續(xù)查找
                  j--
              }
          }
          if(i >= j) {
              // 結(jié)束了, 記錄基準(zhǔn)值的角標(biāo) j
              mid = j
              break
          }
          // i 從前向后找比 base 大的數(shù), 并放到基準(zhǔn)值右側(cè)
          while(i !== j) {
              if(arr[i] > base) {
                  // 找到了, 與基準(zhǔn)值交換位置
                  arr[j] = arr[i]
                  arr[i] = base  // i 總是指向基準(zhǔn)值
                  break
              } else {
                  // 沒找到, 則向后移動(dòng)角標(biāo), 繼續(xù)查找
                  i++
              }
          }
          if(i >= j) {
              // 結(jié)束了, 記錄基準(zhǔn)值的角標(biāo) i
              mid = i
              break
          }
      }
      // 左分區(qū)
      sort(arr, begin, mid-1)
      // 右分區(qū)
      sort(arr, mid + 1, last)
  }
  let arr = [53, 16, 88, 79, 93, 19, 47, 20]
  //          0   1   2   3   4   5   6  7
  let i = 0, j = arr.length - 1
  sort(arr, i, j)
  

• 交換法
  思路：

  1. 分別設(shè)置左右兩個(gè)指針：i=begin, j=last
  2. 以左側(cè)第一個(gè)元素為基準(zhǔn)時(shí)扇苞，先移動(dòng)右側(cè)指針j（稍后解釋為什么）
  3. 當(dāng)j遇到比基準(zhǔn)小的數(shù)時(shí)，停止掃描寄纵；開始掃描左側(cè)指針i
  4. 當(dāng)i遇到比基準(zhǔn)大的數(shù)時(shí)鳖敷，停止掃描，并交換i和j處的值程拭，此時(shí)i處的元素值一定比基準(zhǔn)小
  5. 繼續(xù)移動(dòng)指針j定踱，重復(fù)步驟3-4，直到j與i相遇恃鞋，則交換基準(zhǔn)與i/j處的元素值崖媚；
  6. 至此，第一個(gè)分區(qū)完成恤浪〕┭疲基準(zhǔn)值左側(cè)一定是比基準(zhǔn)小的數(shù)，基準(zhǔn)值右側(cè)是比基準(zhǔn)大的數(shù)水由，然后分別對左分區(qū)和有分區(qū)進(jìn)行排序荠呐。

  注：為什么先移動(dòng)右指針j？當(dāng)然，這不是絕對的泥张，這取決于基準(zhǔn)的位置呵恢，因?yàn)楫?dāng)兩個(gè)指針相遇時(shí)，需要與基準(zhǔn)交換元素值圾结。當(dāng)基準(zhǔn)值在左邊時(shí)瑰剃，必須確保指針相遇的值一定比基準(zhǔn)小，而左指針i 始終指向小于基準(zhǔn)值的元素筝野，所以讓右指針j先移動(dòng)晌姚，讓j向i靠攏，最終相遇歇竟。

  function sort(arr, begin, last) {
      if(begin >= last) {  // 結(jié)束
          return
      }
      let base = arr[begin]
      let i = begin, j = last
      while(i < j) {
          // 先移動(dòng)右側(cè)指針j, 找比基準(zhǔn)值小的數(shù)
          while(i < j && arr[j] >= base) {
              j--
          }
          // 再移動(dòng)左側(cè)指針i, 找比基準(zhǔn)值大的數(shù)
          while(i < j && arr[i] <= base) {
              i++
          }
          if(i < j) {
              // i 記錄比基準(zhǔn)值大的值, j 記錄比基準(zhǔn)值小的值, 交換元素值
              let temp = arr[i]
              arr[i] = arr[j]
              arr[j] = temp
          }
      }
      // 此時(shí) i === j, 且 i 處的元素一定比基準(zhǔn)值小, 交換元素值
      arr[begin] = arr[i]
      arr[i] = base
      // 第一次分區(qū)結(jié)束, 以基準(zhǔn)值的位置i 為分區(qū)線, 遞歸分區(qū)比較
      // 1. 左側(cè)分區(qū)
      sort(arr, begin, i - 1)
      // 2. 右側(cè)分區(qū)
      sort(arr, i + 1, last)
  }
  

【快速排序】是不穩(wěn)定的挥唠，它的速度與【基準(zhǔn)點(diǎn)】有關(guān)，【基準(zhǔn)點(diǎn)】的好壞大大影響速度焕议。

• 最差情況下宝磨，劃分由 n 個(gè)元素構(gòu)成的數(shù)組需要進(jìn)行 n 次比較和 n 次移動(dòng)，因此劃分所需時(shí)間為 O(n)盅安。最差時(shí)間復(fù)雜度 (n-1)+(n-2)+…+2+1= O(n^2)
• 在最佳情況下唤锉，每次將數(shù)組劃分為規(guī)模大致相等的兩部分。和【歸并排序】的分析相似别瞭，快速排序的T(n) = O(nlogn)

求數(shù)組中第K個(gè)最大（辛椤）元素

思路：這也是分治思想的應(yīng)用，與【快速排序】類似蝙寨。但不同的是晒衩，【快速排序】每次都要處理基準(zhǔn)兩側(cè)的分區(qū)，而【求第K個(gè)最大（星酵帷）元素】只需要處理一側(cè)分區(qū)即可听系。

求最接近原點(diǎn)的 K 個(gè)點(diǎn)

找出最大子序列

求 x 的 n 次冪

棋盤覆蓋問題

整數(shù)劃分問題

全排列問題

漢諾塔問題

大整數(shù)乘法

快速傅里葉變換

循環(huán)比賽日程表