五大基础算法——分治算法

分治算法 是一种通过将问题分解为多个规模较小的子问题,递归解决子问题,然后将子问题的解合并为原问题解的算法思想。它通常包含三个步骤:分解(Divide)解决(Conquer)合并(Combine)。以下是分治算法的核心概念、适用场景、实现方法及经典例题:


一、核心概念

  1. 分解(Divide)
    • 将原问题分解为若干个规模较小的子问题。
  2. 解决(Conquer)
    • 递归解决子问题。如果子问题规模足够小,则直接求解。
  3. 合并(Combine)
    • 将子问题的解合并为原问题的解。

二、适用场景

  1. 排序算法
    • 如归并排序、快速排序。
  2. 查找算法
    • 如二分查找。
  3. 数学问题
    • 如大整数乘法、矩阵乘法(Strassen算法)。
  4. 数据结构操作
    • 如最近点对问题、最大子数组问题。

三、实现步骤

  1. 分解问题
    • 将原问题分解为若干个规模较小的子问题。
  2. 递归求解
    • 对每个子问题递归调用分治算法。
  3. 合并结果
    • 将子问题的解合并为原问题的解。

四、经典例题与代码

1. 归并排序

问题描述:将一个无序数组排序。

def mergeSort(arr):if len(arr) <= 1:  # 基线条件return arrmid = len(arr) // 2left = mergeSort(arr[:mid])  # 分解并递归解决左半部分right = mergeSort(arr[mid:])  # 分解并递归解决右半部分return merge(left, right)  # 合并左右部分def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
print(mergeSort(arr))  # 输出 [3, 9, 10, 27, 38, 43, 82]
2. 快速排序

问题描述:将一个无序数组排序。

def quickSort(arr):if len(arr) <= 1:  # 基线条件return arrpivot = arr[len(arr) // 2]  # 选择基准值left = [x for x in arr if x < pivot]  # 分解为小于基准值的子问题middle = [x for x in arr if x == pivot]  # 分解为等于基准值的子问题right = [x for x in arr if x > pivot]  # 分解为大于基准值的子问题return quickSort(left) + middle + quickSort(right)  # 递归解决并合并# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
print(quickSort(arr))  # 输出 [3, 9, 10, 27, 38, 43, 82]
3. 二分查找

问题描述:在有序数组中查找目标值。

def binarySearch(arr, target):if not arr:  # 基线条件return -1mid = len(arr) // 2if arr[mid] == target:return midelif arr[mid] < target:result = binarySearch(arr[mid+1:], target)return result + mid + 1 if result != -1 else -1else:return binarySearch(arr[:mid], target)# 示例
arr = [1, 3, 5, 7, 9]
print(binarySearch(arr, 5))  # 输出 2
4. 最大子数组问题

问题描述:找到一个数组中具有最大和的连续子数组。

def maxSubArray(nums):def divideAndConquer(left, right):if left == right:  # 基线条件return nums[left]mid = (left + right) // 2# 递归解决左半部分和右半部分left_max = divideAndConquer(left, mid)right_max = divideAndConquer(mid+1, right)# 计算跨越中点的最大子数组和cross_max = maxCrossingSum(left, mid, right)return max(left_max, right_max, cross_max)def maxCrossingSum(left, mid, right):left_sum = float('-inf')current_sum = 0for i in range(mid, left-1, -1):current_sum += nums[i]left_sum = max(left_sum, current_sum)right_sum = float('-inf')current_sum = 0for i in range(mid+1, right+1):current_sum += nums[i]right_sum = max(right_sum, current_sum)return left_sum + right_sumreturn divideAndConquer(0, len(nums)-1)# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出 6

五、分治算法的优缺点

优点
  1. 问题分解清晰
    • 将复杂问题分解为简单子问题,易于理解和实现。
  2. 适合并行计算
    • 子问题通常相互独立,适合并行处理。
  3. 高效解决复杂问题
    • 如排序、查找、数学计算等问题。
缺点
  1. 递归开销
    • 递归调用可能导致栈溢出或额外开销。
  2. 子问题重叠
    • 子问题可能重复计算,需结合动态规划优化。
  3. 实现复杂度高
    • 某些问题的分解和合并逻辑较复杂。

六、适用问题特征

  • 问题可以分解为多个独立的子问题。
  • 子问题的解可以合并为原问题的解。
  • 常见问题包括:排序、查找、数学计算、数据结构操作等。

分治算法是一种强大的工具,适合解决复杂问题。在实际应用中,需注意子问题的独立性和合并逻辑,必要时结合其他算法(如动态规划)进行优化。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34823.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DeepSeek-R1思路训练多模态大模型-Vision-R1开源及实现方法思路

刚开始琢磨使用DeepSeek-R1风格训练多模态R1模型&#xff0c;就看到这个工作&#xff0c;本文一起看看&#xff0c;供参考。 先提出问题&#xff0c;仅靠 RL 是否足以激励 MLLM 的推理能力&#xff1f; 结论&#xff1a;不能&#xff0c;因为如果 RL 能有效激励推理能力&#…

Python学习第十八天

Django模型 定义&#xff1a;模型是 Django 中用于定义数据库结构的 Python 类。每个模型类对应数据库中的一张表&#xff0c;类的属性对应表的字段。 作用&#xff1a;通过模型&#xff0c;Django 可以将 Python 代码与数据库表结构关联起来&#xff0c;开发者无需直接编写 S…

总结 HTTP 协议的基本格式, 相关知识以及抓包工具fiddler的使用

目录 1 HTTP是什么 2 HTTP协议格式 3 HTTP请求(Request) 3.1 认识URL 3.2 方法 3.3 认识请求"报头"(header) 3.3.1 Host 3.3.2 Content-Length 3.3.3 Content-Type 3.3.4 User-Agent (简称UA) 3.3.5 Referer 3.3.6 Cookie和Session 4 HTTP响应详解 4.…

【sql靶场】第15、16关-post提交盲注保姆级教程

目录 【sql靶场】第15、16关-post提交盲注保姆级教程 1.知识回顾 ‌GET请求‌ ‌POST请求‌ or与and 2.第十五关 1.布尔盲注的手动注入 1.判断 2.数据库名长度 3.数据库名字符 4.表名数 5.表名长度 6.表名符 7.字段数 8.字段长度 9.字段符 2.布尔盲注的脚本注入…

【C++】 —— 笔试刷题day_6

刷题day_6&#xff0c;继续加油哇&#xff01; 今天这三道题全是高精度算法 一、大数加法 题目链接&#xff1a;大数加法 题目解析与解题思路 OK&#xff0c;这道题题目描述很简单&#xff0c;就是给我们两个字符串形式的数字&#xff0c;让我们计算这两个数字的和 看题目我…

redis终章

1. 缓存(cache) Redis最主要的用途&#xff0c;三个方面1.存储数据&#xff08;内存数据库&#xff09;&#xff1b;2.缓存[redis最常用的场景]&#xff1b;3.消息队列。 缓存(cache)是计算机中的⼀个经典的概念.核⼼思路就是把⼀些常⽤的数据放到触⼿可及(访问速度更快)的地⽅…

Matlab 多输入系统极点配置

1、内容简介 略 Matlab 172-多输入系统极点配置 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 clc close all clear A [-6.5727 1.1902 0 -53.4085;1.1902 -6.5727 0 -53.4085;0.5294 0.5294 0 17.7502;0 0 1 0]; B [1.3797 -0.2498;-0.2498 1.3797;-0.1111 -0.1…

国产编辑器EverEdit - 脚本(解锁文本编辑的无限可能)

1 脚本 1.1 应用场景 脚本是一种功能扩展代码&#xff0c;用于提供一些编辑器通用功能提供不了的功能&#xff0c;帮助用户在特定工作场景下提高工作效率&#xff0c;几乎所有主流的编辑器、IDE都支持脚本。   EverEdit的脚本支持js(语法与javascript类似)、VBScript两种编程…

Flutter 小技巧之通过 MediaQuery 优化 App 性能

许久没更新小技巧系列&#xff0c;温故知新&#xff0c;在两年半前的《 MediaQuery 和 build 优化你不知道的秘密》 我们聊过了在 Flutter 内 MediaQuery 对应 rebuild 机制&#xff0c;由于 MediaQuery 在 MaterialApp 内&#xff0c;并且还是一个 InheritedWidget &#xff0…

AI-医学影像分割方法与流程

AI医学影像分割方法与流程–基于低场磁共振影像的病灶识别 – 作者:coder_fang AI框架&#xff1a;PaddleSeg 数据准备&#xff0c;使用MedicalLabelMe进行dcm文件标注&#xff0c;产生同名.json文件。 编写程序生成训练集图片&#xff0c;包括掩码图。 代码如下: def doC…

【蓝桥杯每日一题】3.16

&#x1f3dd;️专栏&#xff1a; 【蓝桥杯备篇】 &#x1f305;主页&#xff1a; f狐o狸x 目录 3.9 高精度算法 一、高精度加法 题目链接&#xff1a; 题目描述&#xff1a; 解题思路&#xff1a; 解题代码&#xff1a; 二、高精度减法 题目链接&#xff1a; 题目描述&…

人工智能组第一次培训——deepseek本地部署和知识库的建立

deepseek本地部署的用处 减少对网络依赖性&#xff1a; 在断网环境下&#xff0c;依然可以使用预先下载的AI模型进行处理&#xff0c;避免因网络不稳定而无法完成任务。 提高响应速度&#xff1a; 数据和模型已经在本地设备上准备好&#xff0c;可以直接调用&#xff0c;不…

windows协议不再续签,华为再无windows可用,将于四月发布鸿蒙PC

大家好&#xff0c;我是国货系创始人张云泽&#xff0c;最近不少小伙伴在后台问&#xff1a;“听说Windows协议要到期了&#xff1f;我的电脑会不会变砖&#xff1f;”还有人说&#xff1a;“华为笔记本以后用不了Windows了&#xff1f;鸿蒙系统能用吗&#xff1f;”今天咱们就…

数据结构-----初始数据结构、及GDB调试

一、数据结构核心概念 相互之间存在一种或多种特定关系的数据元素的集合。 1. 数据结构定义 // 嵌入式场景示例&#xff1a;传感器网络节点结构 struct SensorNode {uint16_t node_id; // 2字节float temperature; // 4字节uint32_t timestamp; // 4字节struct Se…

HOT100(1)

目前想到的办法是暴力枚举&#xff0c;有什么更好的办法请多指教。。。。代码如下&#xff1a; 让数组第一个元素和后面的元素相加判断是否相等&#xff0c;让数组第二个元素与后面的元素相加判断是否相等&#xff0c;以此类推 /** * Note: The returned array must be mallo…

QuickAPI 和 DBAPI 谁更香?SQL生成API工具的硬核对比(一)

最近低代码开发火得不行&#xff0c;尤其是能把数据库秒变API的工具&#xff0c;简直是开发者的救星。今天咱就聊聊两款国内玩家&#xff1a;QuickAPI&#xff08;麦聪软件搞出来的低代码神器&#xff09;和 DBAPI&#xff08;开源社区的硬核作品&#xff09;。这两货都能靠SQL…

MySQL单表查询大全【SELECT】

山再高&#xff0c;往上攀&#xff0c;总能登顶&#xff1b;路再长&#xff0c;走下去&#xff0c;定能到达。 Mysql中Select 的用法 ------前言------【SELECT】0.【准备工作】0.1 创建一个库0.2 库中创建表0.3 表中加入一些数据 1.【查询全部】2.【查询指定列】2.1查询指定列…

开启云服务器ubuntu22.04的远程桌面,支持Windows远程连接 - 开启XRDP支持

效果图 环境 云服务器 Ubuntu 22.04 lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.5 LTS Release: 22.04 Codename: jammy 本地windows10 步骤 前置动作 # 远程登录 ssh rootx.x.x.x# 看看硬盘够不够空间&…

虚拟化数据恢复—重装系统服务器崩了的数据恢复过程

虚拟化数据恢复环境&故障&#xff1a; VMware虚拟化平台 vmfs文件系统 工作人员误操作重装操作系统&#xff0c;服务器崩溃。 重装系统会导致文件系统元文件被覆盖。要恢复数据&#xff0c;必须找到&提取重装系统前的文件系统残留信息&#xff0c;通过提取出来的元文件…

harmonyOS NEXT开发与前端开发深度对比分析

文章目录 1. 技术体系概览1.1 技术栈对比1.2 生态对比 2. 开发范式比较2.1 鸿蒙开发范式2.2 前端开发范式 3. 框架特性对比3.1 鸿蒙 Next 框架特性3.2 前端框架特性 4. 性能优化对比4.1 鸿蒙性能优化4.2 前端性能优化 5. 开发工具对比5.1 鸿蒙开发工具5.2 前端开发工具 6. 学习…