8

如何使用分治算法的思想，分治技巧详解 - ZhanLi

 1 year ago
source link: https://www.cnblogs.com/ricklz/p/16898388.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

分治算法的思想

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

分治算法和递归的区别

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

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

分解：将原问题分解成一系列子问题；

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

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

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

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

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

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

1、二分搜索

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

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

输入: 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 的次数。

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

输入：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/归并排序
【归并排序】https://geekr.dev/posts/go-sorting-algorithm-merge
【分治使用技巧】https://boilingfrog.github.io/2022/11/17/分治算法的思想/


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK