分治算法学习笔记

2024-07-03 14:39| 来源: 网络整理| 查看: 265

分治算法（Divide and Conquer）算法

分治，“分而治之”，即把一个复杂的问题分成两个或者更多的相同的或者相似的子问题，再把子问题分成更小的子问题，直到最后的子问题可以简单的求解，原问题的解就是子问题解的合并

基本思想

分治算法在每一层的递归上都有三个步骤：分解：将原问题分解为规模更小、相互独立且与原问题形式相同的子问题求解：如果子问题的规模足够小，可以很容易解决则直接解决，否则，进入下一层递归合并：将求得的子问题的解合并为上一个原问题的解，直到合并为最初原问题的解

适用问题该问题的规模缩小的一定程度可以比较简单地解决该问题可以分解为若干规模较小的相同问题利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题时间复杂度

分治算法将规模为 n n n 的问题分为 k k k 个规模为 n / k n/k n/k 的子问题解决。

设分解阈值为 n 0 = 1 n_0 = 1 n0=1；且求解规模为 1 1 1 的问题需耗费 1 1 1 个单位时间；

再设将原问题分解为 k k k 个子问题，以及合并 k k k 个子问题的解合并为原问题的解需要用 f ( n ) f(n) f(n) 个单位时间；

用 T ( n ) T(n) T(n) 表示使用该分治算法求解规模为 n n n 的问题所需的时间，则有： T ( n ) = k ∗ T ( n / k ) + f ( n ) T(n) = k*T(n/k) + f(n) T(n)=k∗T(n/k)+f(n)

案例之二分查找

二分查找是典型的分治算法的应用，将原有的有序数列划分为左右两个子序列，然后再对两个子序列中的其中一个进行划分，直到查找成功

算法流程

二分查找的前提：必须是有序数列

算法流程：（查找一个数）

选择一个标志 i 将数列分为左右两个数列判断 L[i] 是否与要查找的数 ans 相等，相等则返回 i否则，判断 L[i] 与 ans 的大小基于第三步的结果，决定之后是向左寻找还是向右寻找递归，直到找到数 ans，或者确定数组 L 中找不到代码示例 Python ''' 最基础的二分查找算法在一个有序的数列中，寻找特定元素的位置如果找到搜索的数，则返回其索引，否则返回 None ''' def basic_BinarySearch(search_list, item): low = 0 high = len(search_list)-1 while low item: high = mid - 1 else: low = mid + 1 return None ''' 寻找左边界的二分查找算法 ''' def left_BinarySearch(search_list, item): if not search_list: return None low = 0 high = len(search_list) # 与 basic 不同 while low = item: high = mid else: low = mid + 1 return low ''' 寻找右边界的二分查找算法 ''' def right_BinarySearch(search_list, item): if not search_list: return None low = 0 high = len(search_list) while low int mid = low + (high - low) / 2; int temp = nums[mid]; if (temp == item) { return mid; } else if (temp high = mid - 1; } } return -1; } /** * 寻找左边界的二分查找算法 * 在有序数组中查找 nums 中元素是否存在大于等于 item * 如果存在，返回第一个大于等于 item 的元素的索引，否则返回 -1 * */ public static int leftBinarySearch(int[] nums, int item) { if (nums[0] >= item) { return 0; } if (nums[nums.length - 1] int mid = low + (high - low) / 2; if (nums[mid] >= item) { high = mid; } else { low = mid + 1; } } return low; } /** * 寻找右边界的二分查找算法 * 在有序数组中查找 nums 中元素是否存在小于等于 item * 如果存在，返回最后一个小于等于 item 的元素的索引，否则返回 -1； * */ public static int rightBinarySearch(int[] nums, int item) { if (nums[0] > item) { return -1; } if (nums[nums.length - 1] int mid = low + (high - low) / 2; if (nums[mid] high = mid; } } return low - 1; } 案例之全排列问题 LeetCode 题目 46

给定一个没有重复数字的序列，返回其所有可能的全排列

示例：

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 问题分析

采用分治思想，首先要把大问题分解为很多子问题，大问题是所有的排列方法；分解得到的子问题就是：以 1 开头的排列、以 2 开头的排列、以 3 开头的排列；

现有的子问题仍可继续分解，例如，以 1 开头的子问题，确定了 1 的位置，但是没有确定 2、3 的位置，可以继续分解，直到分解成的子问题只有一个数字，不再分解

代码示例 Python def permute(self, nums: List[int]) -> List[List[int]]: def fullSort(sort_nums: List[int], start: int, end: int): if start == end: res.append(nums[:]) else: for i in range(start, end): temp = sort_nums[start] sort_nums[start] = sort_nums[i] sort_nums[i] = temp fullSort(sort_nums, start+1, end) sort_nums[i] = sort_nums[start] sort_nums[start] = temp end = len(nums) res = [] fullSort(nums, 0, end) return res Java /** * 给定一个没有重复数字的序列，返回其所有可能的全排列 * */ public static List permute(int[] nums) { int end = nums.length; List result = new ArrayList(); List answer = new ArrayList(); for (int num : nums) { answer.add(num); } permuteAdd(result, answer,0, end); return result; } public static void permuteAdd(List result, List answer, int start, int end) { if (start == end) { result.add(new ArrayList(answer)); } for (int i = start; i public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 9, 0, 29}; int[] temp = new int[arr.length]; mergerSort(arr, 0, arr.length - 1, temp); System.out.println(Arrays.toString(arr)); } // 分解过程 public static void mergerSort(int[] arr, int left, int right, int[] temp) { if (left int i = left; // 表示左边有序序列的初始索引 int j = mid + 1; // 表示右边有序序列的初始索引 int t = 0; // 指向 temp 的当前索引 // 先把左右两边有序的数据按照规则填充到 temp 中 // 直到左右两边的有序序列，有一边处理完毕 while (i temp[t] = arr[i]; t += 1; i += 1; } else { temp[t] = arr[j]; t += 1; j += 1; } } // 把剩余的一个序列，全部填充到 temp while (i temp[t] = arr[j]; t += 1; j += 1; } // 把 temp 复制到 arr // 并不是每次都拷贝所有的数据 t = 0; int tempLeft = left; while (tempLeft public static void main(String[] args) { int[] arr = {-9, 78, 0, 23, -5, 70, 900, -560, 893}; System.out.println(Arrays.toString(arr)); quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int left, int right) { int l = left; // 左下标 int r = right; // 右下标 int pivot = arr[(left + right) / 2]; int temp; // 通过 while 循环，将比 pivot 值小的放到左边 // 将比 pivot 值大的放到右边 while (l l += 1; } // 找到比 pivot 值大于等于的值 while (arr[r] > pivot) { r -= 1; } if (l >= r) { // 说明 pivot 左右两边的值满足 break; // 左边小于 pivot；右边大于 pivot } else { // l < r temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // 如果交换完后， arr[l] == pivot，r--，前移 if (arr[l] == pivot) { r -= 1; } // 如果交换完后，arr[r] == pivot，l++，后移 if (arr[r] == pivot) { l += 1; } } } // 一定要做如下判断，否则出现栈溢出 // 因为是满足上述条件的，无法从循环中退出 if (l == r) { l += 1; r -= 1; } if (left quickSort(arr, l, right); } } }

更多排序算法详解

案例之汉诺塔（Hanoi Tower）汉诺塔问题

一个梵塔，塔内有三个盘座A、B、C，A上有64个盘子，盘子大小不等，大在下，小在上。若要把盘子从A移到B，每次只能移动一个，且移动过程中，3个座上始终保持：大在上，小在下

问题分析如果只有一个盘子，则不需要借助C，直接从A移动到B如果只有两个盘子，则可以先把A的最上面一个盘子2移动到C；将盘子1移动到B；再讲盘子2移动到B。；这说明了借助C可以将2个盘子从A移动到B；同样，也说明借助B可以将2个盘子从A移动到C如果有3个盘子，那么根据2个盘子的结论，可以借助B将盘子1上的两个盘子（盘子2和盘子3）从A移动到C；将盘子1从A移动到B，A则变为空座；借助A座，将C上的两个盘子移动到B以此类推，上述思路可以扩展到 n 个盘子的情况，将较小的 n-1 个盘子看做一个整体，也就是我们要求的子问题，初始A上有 n 个盘子，B、C上为空；可以借助B，将A上面的 n-1 个盘子从A移动到C；将A上最大的盘子1移动到B，A为空座；；可以借助B，将C上的 n-2 个盘子从C移动到A；将C上最大的盘子2（从整体看，为第二大）移动到B，C为空座；；… 代码示例 def move(n, source, target): print('The', n, 'th', 'plate move: ', source, '------>', target) def hanoi(n, source, temp, target): if n == 1: # only one plate, move it directly from source to target move(n, source, target) else: # move the top n-1 plates from source to temp through target hanoi(n-1, source, target, temp) # move the n plate(the largest and lowest plate) from source to target move(n, source, target) # move the top n-1 plates from temp to target through source hanoi(n-1, temp, source, target) hanoi(3, 'A', 'C', 'B')

【本文地址】

公司简介

联系我们