分治策略

分治策略

一般方法

给定函数来计算n个输入, 分治策略 建议将输入分成k个子集,1<k<=n,得到k个子问题

解递归关系

很多分治算法的复杂度是这样的

$$T(n)= a_{1}^n $$

残缺棋盘

描述: 有2k* 2k个方格的棋盘中恰好有一个方格是坏的

要求:用三方块把残缺棋盘铺满,三方块不能重叠,不能盖住坏的方格

—–> 需要用(22k-1)/3个三方块

解决思路(分治法):

  1. 划分成小棋盘比如4个2k-1* 2k-1,这样只有一个小棋盘有坏的
  2. 我们用一个三方块盖住没有坏方格的三个棋盘
  3. 递归
  4. 棋盘的大小缩为1*1时,递归终止

二分搜索

描述: 在n个已经按升序/降序排列好的元素中搜索是否存在元素x

要求: 已经按 升序/降序 排列好