如何使用分治算法的思想,分治的技巧详解

如何使用分治,有哪些需要注意的点

Posted by liz on November 17, 2022

分治算法

分治算法的思想

分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。

分治算法和递归的区别

分治是处理问题的思想,递归是一种编程技巧。分治一般都比较适合用用递归来实现。

分治算法的实现中,每一层地递归都会涉及到下面三个操作:

分解:将原问题分解成一系列子问题;

解决:将子问题的结果合并成原问题。

使用分治算法需要满足的条件

1、原问题与分解成的小问题具有相同的模式;

2、原问题分解成的子问题可以独立求解,子问题之间没有相关性;

3、具有分解终止条件,也就是说,当问题足够小时,可以直接求解;

4、可以将子问题合并成原问题,而这个合并操作的复杂度不能太高,否则就起不到减小算法总体复杂度的效果了。

经典题目

1、二分搜索

给定一个n个元素有序的(升序)整型数组nums 和一个目标值target ,写一个函数搜索nums中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 

示例2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

题目链接:https://leetcode.cn/problems/binary-search

解题思路

1、满足分支算法的思想,将为题分解为规模较小的相同问题时,就比较容易求解;

2、找出中间的值和目标值进行比较,通过判断大小,来不断的缩小问题的求解范围;

3、这样每次的求解,总是能将问题的范围缩小一半,或者找出目标值。

时间复杂度:O(logn)

空间复杂度:O(1)

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right + left) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		}
	}

	return -1
}

2、第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1:

输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5)-> true
调用 isBadVersion(4)-> true
所以,4 是第一个错误的版本。

示例 2:

输入:n = 1, bad = 1
输出:1

链接:https://leetcode.cn/problems/first-bad-version

题解:

这道题目是二分查找的变种题目,找出最近的一个出错的版本,也就是出错版本的左边都是出错的版本;

所以利用二分查找,找出出错的又边界即可

/**
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return 	 	      true if current version is bad
 *			          false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
	left, right := 0, n
	for left < right {
		mid := (right + left) / 2
		if isBadVersion(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return right
}

// 测试函数
func isBadVersion(n int) bool {
	return false
}

3、快速排序

快速排序在我们刚学习算法的时候就遇到了过了,其中它使用到的算法思想就是分治策略。

它的处理思路就是,会选中一个基准数,通过一趟排序,和当前的基准数进行比较,将数据分总成两部分,一部分大于基准数,另一部分小于基准数。

然后对这两部分数据在进行上面的操作,直到所有的数据都有序,整个排序的过程可以使用递归去实现。

快排的时间复杂度:平均情况下快速排序的时间复杂度是Θ(nlgn),最坏情况是n2

空间复杂度:最好空间复杂度为 O(logn),最坏空间复杂度为 O(n)

上代码

func QuickSort(arr []int) {
	quickSort(arr, 0, len(arr)-1)
}

func quickSort(data []int, l, u int) {
	if l < u {
		m := partition(data, l, u)
		quickSort(data, l, m-1)
		quickSort(data, m, u)
	}
}

func partition(data []int, l, u int) int {
	quick := data[l]
	left := l

	for i := l + 1; i <= u; i++ {
		if data[i] <= quick {
			left++
			data[left], data[i] = data[i], data[left]
		}
	}
	data[l], data[left] = data[left], data[l]
	return left + 1
}

4、归并排序

归并排序也是使用分治思想实现的一个比较经典的栗子,这里来分析下

归并排序的处理思路:

1、首先拆分子序列,使得子序列很容易排序,然后对子序列进行排序;

2、然后是合并的过程,将有序的子序列合并;

3、合并子序列的过程;

  • 1、申请空间,大小为两个已经排好序的子序列大小之和,该空间用来存放合并后的序列;

  • 2、设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  • 3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  • 4、重复步骤3直到某一指针超出序列尾;

  • 5、将剩下的元素直接复制到合并序列尾部;

divide

具体的动画细节

divide

上代码

时间复杂度 O(nlogn)

空间复杂度 O(n)

func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	leftArr := MergeSort(arr[0:mid])
	rightArr := MergeSort(arr[mid:])
	return merge(leftArr, rightArr)
}

func merge(left, right []int) []int {
	i, j := 0, 0
	m, n := len(left), len(right)
	var result []int
	// 合并子序列
	for {
		// 任何一个区间遍历完成就退出
		if i >= m || j >= n {
			break
		}
		if left[i] > right[j] {
			result = append(result, right[j])
			j++
		} else {
			result = append(result, left[i])
			i++
		}
	}

	// 左边的子集没有遍历完成,将左侧的放入到结果集
	if i < m {
		result = append(result, left[i:]...)
	}

	// 右侧的子集没有遍历完成,将右侧的放入到结果集中
	if j < n {
		result = append(result, right[j:]...)
	}

	return result
}

直接在原数组上进行操作

func MergeSort(nums []int) []int {
	mergeSort(nums, 0, len(nums)-1)
	return nums
}

func mergeSort(nums []int, start, end int) {
	if start >= end {
		return
	}
	mid := start + (end-start)/2
	mergeSort(nums, start, mid)
	mergeSort(nums, mid+1, end)
	var tmp []int
	i, j := start, mid+1
	for i <= mid && j <= end {
		if nums[i] > nums[j] {
			tmp = append(tmp, nums[j])
			j++
		} else {
			tmp = append(tmp, nums[i])
			i++
		}
	}
	if i <= mid {
		tmp = append(tmp, nums[i:mid+1]...)
	}
	if j <= end {
		tmp = append(tmp, nums[j:end+1]...)
	}
	for i := start; i <= end; i++ {
		nums[i] = tmp[i-start]
	}
}

5、数组中的逆序对

题目地址:https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

输入: [7,5,6,4]
输出: 5

解题思路

首先用到的是分治算法的思想

1、什么是逆序对,就是前面的数字大小,小于位于其后面的数字大小,那么这就是一个逆序对;

2、这里主要用到了分治的算法,只是在分治算法的基础之上,在进行数据的合并的时候,因为左边部分和右边部分都是已经排好序了,所以可以使用这种关系,来计算逆序对的个数;

3、具体的合并计算过程;

  • 1、在左边和右边数组中,都从第一个下标,开始匹配;

  • 2、如果左边当前下标的数大于右边数组当前下标的值,因为这两个数组都是从大到小排序的,所有左边从当前下标开始数,都大于右边当前匹配下标的数,cnt += mid - i + 1,同时右边数组下标前移;

  • 3、如果左边当前下标的数小于右边数组当前下标的值,不满足,左边数组下标前移;

func reversePairs(nums []int) int {
	return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, start, end int) int {
	if start >= end {
		return 0
	}
	mid := start + (end-start)/2
	cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end)
	tmp := []int{}
	i, j := start, mid+1
	for i <= mid && j <= end {
		if nums[i] > nums[j] {
			tmp = append(tmp, nums[j])
			cnt += mid - i + 1
			j++
		} else {
			tmp = append(tmp, nums[i])
			i++
		}
	}
    
    if i <= mid {
        tmp = append(tmp, nums[i:mid+1]...)
    }
    if j <= end{
        tmp = append(tmp, nums[j:end+1]...)
    }
	for i := start; i <= end; i++ {
		nums[i] = tmp[i-start]
	}
	return cnt
}

6、汉诺塔

汉诺塔问题的描述:

假设有 A、B、C 三根柱子。其中在 A 柱子上,从下往上有 N 个从大到小叠放的盘子。我们的目标是,希望用尽可能少的移动次数,把所有的盘子由 A 柱移动到 C 柱。过程中,每次只能移动一个盘子,且在任何时候,大盘子都不可以在小盘子上面。

解题思路:

尝试把问题分解,使用分治的思想,将问题分解成一个个容易解决的子问题,然后一个个的去解决

我们把一个 N 层汉诺塔从 A 搬到 C,我们假定只有两层,首先把 N-1 层搬到 B,然后把下面的第 N 层搬到 C,然后再把 N-1 层从 B 搬到 C 。

如果存在多层,那我们就假定 N-1 层已经排好序了,只搬第 N 层,这样依次递归下去。

终止条件:

当只剩下最后一个的时候,我们只需要搬动一次就行了

var count int = 0

func main() {
	beadNum := 5 // This is the initial number of beads
	hanoi(beadNum, "A", "B", "C")
	fmt.Println(count)
}

func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
	if beadNum == 1 {
		// 最后一个了,可以结束了
		move(beadNum, pillarA, pillarC)
	} else {
		// Step 2: 将 N-1 层从 A 移动到 B
		hanoi(beadNum-1, pillarA, pillarC, pillarB)
		// Step 2: 将第 N 层从 A 移动到 C
		move(beadNum, pillarA, pillarC)
		// Step 3: 将 B 中的 N-1 层移动到 C
		hanoi(beadNum-1, pillarB, pillarA, pillarC)
	}
}

func move(beadNum int, pillarFrom string, pillarTo string) {
	count += 1
}

总结

1、分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。

2、分治是处理问题的思想,递归是一种编程技巧。分治一般都比较适合用用递归来实现。

3、分治算法的实现中,每一层地递归都会涉及到下面三个操作:

  • 分解:将原问题分解成一系列子问题;

  • 解决:将子问题的结果合并成原问题。

参考

【数据结构与算法之美】https://time.geekbang.org/column/intro/100017301
【经典优化算法之分治法】https://zhuanlan.zhihu.com/p/45986027
【归并排序】https://zh.m.wikipedia.org/zh-hans/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
【归并排序】https://geekr.dev/posts/go-sorting-algorithm-merge