《算法设计与分析》课件 chp3分治法

分治法算法设计的核心思想从运动会组织说起在组织全校运动会时,可以将复杂工作分解为几个主要部分:体育项目安排、场地布置、奖品准备、宣传和报名等。每个部分由专门小组负责,各小组独立工作。最终,项目负责人协调整合所有成果,确保各部分顺利对接。这个例子体现了将复杂问题分而治之、逐个击破的思想,这正是分治法的核心理念。基本思想01分解将原问题分解为若干个规模较小的子问题,这些子问题与原问题形式相同但规模更小02解决递归地求解各个子问题。当子问题规模足够小时,可以直接求解03合并将子问题的解合并,得到原问题的解一个简单的例子:求数组最大值给定包含n个元素的数组A,如何求出其中最大的元素?传统方法逐个比较,寻找最大值。时间复杂度为Θ(n),需要遍历整个数组。分治思路将数组A划分成两部分,分别找到每部分的最大值,然后取二者中的较大者作为数组A的最大值。分治法求最大值算法对于数组A=[34,12,56,98,23,45,67,89],求解其最大值的过程:分解将数组分成A₁=[34,12,56,98]和A₂=[23,45,67,89]递归求解A₁的最大值为98,A₂的最大值为89合并max(98,89)=98,即为数组A的最大值时间复杂度分析算法的基本操作为比较。假设对于长度为n的数组找其最大值需要的基本操作次数为C(n),则递推公式如下:使用替换法求解,最终得到C(n)=n-1。可见,通过分治法求最大值所需的比较次数与顺序比较方法是一样的,都是n-1次。分治算法的时间复杂度对于规模为n的问题,时间复杂度T(n)由三部分组成:分解阶段

递归求解假设子问题数量为a,每个子问题规模为n/b,则时间复杂度为aT(n/b)合并阶段

主定理

情况一

情况二

情况三

归并排序排序问题是将数组按照从小到大或从大到小的顺序重新排列。例如,给定输入数组A=[3,4,1,5,2,7,9,8],将其按从小到大排序后得到[1,2,3,4,5,7,8,9]。利用分治法解决排序问题的步骤:分解:将数组A划分为两个子数组[3,4,1,5]和[2,7,9,8]解决:递归地对子数组进行排序,得到[1,3,4,5]和[2,7,8,9]合并:将两个有序子数组合并为一个有序数组[1,2,3,4,5,7,8,9]归并排序的核心:合并操作如何将两个长度分别为n/2的有序子数组合并为一个长度为n的有序数组?以合并两个子数组[1,5,7]和[2,6,8]为例最后得到合并后的有序数组[1,2,5,6,7,8]合并操作的时间复杂度合并过程通过逐步比较两个子数组的当前元素来完成,直至其中一个子数组的所有元素被完全处理。之后,另一个子数组的剩余元素会直接复制到结果数组中。在最坏和最好情况下,比较操作的执行次数都为min(n₁,n₂)次。当主循环结束后,剩余元素的复制不涉及比较操作。复杂度分析时间复杂度:Θ(n)空间复杂度:Θ(n)归并排序的时间复杂度设长度为n的数组所需的比较操作次数为C(n)。归并排序的时间复杂度主要由两部分构成:子数组排序对两个长度为n/2的子数组进行递归排序,时间复杂度为2C(n/2)子数组合并合并两个长度为n/2的有序子数组,时间复杂度为Θ(n)因此,递推公式为:根据主定理,归并排序的时间复杂度为C(n)∈Θ(nlogn)归并排序的空间复杂度空间复杂度主要由两部分组成:递归分解的空间开销递归调用的深度为log₂n,每次递归调用需要常数空间保存函数参数。因此,递归调用栈的空间复杂度为Θ(logn)。合并操作的空间开销合并操作需要额外的存储空间来合并两个有序子数组,空间复杂度为Θ(n)。将两部分相加,归并排序的总空间复杂度为:Θ(logn)+Θ(n)=Θ(n)原地合并算法是否能够设计一种原地合并算法,即在不使用额外数组的情况下,直接在原数组内完成合并操作,从而将合并操作的空间复杂度降低至Θ(1)?以合并A₁=[2,4,6]和A₂=[3,5,7]为例,原地合并的思路是:原地合并算法的代价Θ(1)空间复杂度不使用额外数组,空间复杂度降至常数级Θ(n²)时间复杂度由于需要频繁移动元素,时间复杂度从Θ(n)退化到Θ(n²)快速排序归并排序需要额外的存储空间来存放中间结果,且合并操作的开销较大。那么,是否可以在分治过程中避免合并步骤,直接通过某种方式将数组中的元素重新排列,从而得到一个有序数组?快速排序正是基于这一思路。与归并排序不同,快速排序的核心在于"划分"而非"合并"。快速排序的基本思想假设初始数组为:[3,8,2,9,1,4]选择基准假定基准选择为3划分操作将数组重新排列为:[2,1,3,9,8,4]递归排序对左右两部分递归排序其中,左边部分[2,1]的所有元素均小于基准3,右边部分[9,8,4]的所有元素均大于基准3。在划分操作完成后,基准元素3的位置已经确定。划分算法:辅助数组法给定数组A和基准元素P,划分的目标是将数组A分为两部分,使得左边的所有元素都小于P,右边的所有元素都大于P。一个简单的方法是使用辅助数组B:遍历数组A,如果当前元素小于基准P,则按从左到右的顺序将其放入辅助数组B的左侧;如果当前元素大于基准P,则按从右到左的顺序将其放入辅助数组B的右侧。最终,将基准P放置在辅助数组B的剩余位置。划分算法:辅助数组法辅助数组法：复杂度分析Θ(n)时间复杂度仅需对数组A进行一次扫描Θ(n)空间复杂度需要一个与A相同大小的辅助数组B原地划分:Lomuto算法为了实现空间复杂度为Θ(1)的原地划分,Lomuto算法采用以下策略:从左往右遍历数组,遇到小于基准的元素时,将其交换到数组左边的某一位置。初始-基准为3[3,8,2,9,1,4]188>3,跳过[3,8,2,9,1,4]222<3,与8交换[3,2,8,9,1,4]399>3,跳过[3,2,8,9,1,4]411<3,与8交换[3,2,1,9,8,4]544>3,跳过[3,2,1,9,8,4]6-基准与1交换[1,2,3,9,8,4]步骤当前扫描元素说明数组ALomuto算法的性能分析时间复杂度比较操作需要执行n-1次,因此时间复杂度为Θ(n)最坏情况下,交换操作需要执行n次空间复杂度算法仅需要保存i、j等常数级的变量因此空间复杂度为Θ(1)优化交换次数:Hoare算法Lomuto算法中存在重复交换的问题。Hoare算法通过两端扫描的方式优化了这一点:从左到右扫描,找到一个大于或等于基准元素的值从右到左扫描,找到一个小于基准元素的值交换这两个值对于数组A=[3,8,2,9,1,4],基准为3:从左找到8,从右找到1,交换得到[3,1,2,9,8,4]从左找到9,从右找到2,下标交错,扫描结束交换基准与2,得到[2,1,3,9,8,4]Hoare算法的优势减少交换次数避免重复交换空间复杂度Θ(1)Θ(n)时间复杂度快速排序的时间复杂度快速排序的时间复杂度主要由两部分组成:划分操作的时间(Θ(n))以及递归求解子问题的时间。递归求解子问题的时间取决于划分之后左右子数组的规模。最坏情况划分后数组被分成极端不均衡的两部分,一部分为空,另一部分有n-1个元素。时间复杂度为Θ(n²)最好情况数组被尽可能均匀地分割成两部分。时间复杂度为Θ(nlogn)平均情况假设基准出现在每个位置的概率相同。时间复杂度约为1.39nlogn基准选择的重要性当划分后的两端数组分布极不均衡时,快速排序的时间复杂度会退化至Θ(n²)。特别是当输入数组为有序或近乎有序状态,且始终选择数组首元素作为基准时,会导致一端数组为空。因此,基准的选择对快速排序的性能具有重大影响。基准选择策略随机快速排序随机选取数组中的元素作为基准,而非固定选取首元素。通过随机选择,可以有效规避输入数据特定排列模式所带来的最坏情况。三数取中法从数组的首元素、最后一个元素和中间元素中选择中位数作为基准。这样可以减少最坏情况的发生,平均性能更佳。时间复杂度为Θ(1)。中位数选择直接选取数组中位数作为基准。在能在线性时间内完成中位数选择的前提下,快速排序的时间复杂度将稳定在Θ(nlogn)。快速排序的算法优化非递归实现当处理大型数组时,递归调用的深度可能会导致栈溢出。可以使用显式的栈来模拟递归过程,避免栈溢出问题。小数组优化当数组规模较小时,递归调用的开销相对于排序本身的开销变得显著。可直接调用插入排序来改善这一状况。Sedgewick,Robert."Implementingquicksortprograms."CommunicationsoftheACM21.10(1978):847-857.最大子数组问题最大子数组问题是找到给定整数数组中具有最大和的连续子数组。给定一个长度为n的数组A[1⋯n],要求找到子数组A[i⋯j],使得该子数组的元素之和最大。枚举法的思路是穷举出所有子数组,然后逐一计算子数组的和,在其中选择最大子数组的和。对于长度为n的数组，时间复杂度为：分治法求解最大子数组按照分治法的求解范式:01分解将数组分成两个大致相同长度的子数组02解决递归地求解左半部分数组和右半部分数组的最大子数组03合并需要计算跨越中点的最大子数组,与左、右部分的最大子数组比较,取其中的最大值核心在于合并操作,即计算跨越中点的最大子数组。算法框架跨越中点的最大子数组对于数组A=[2,-1,3,-4,5,-2,1,-3,4],中点为A[5]。向左扩展从A[5]向左扩展,计算最大子数组和:[5]:和为5[-4,5]:和为1[3,-4,5]:和为4[-1,3,-4,5]:和为3[2,-1,3,-4,5]:和为5最大和为5向右扩展从A[5]向右扩展,计算最大子数组和:[-2]:和为-2[-2,1]:和为-1[-2,1,-3]:和为-4[-2,1,-3,4]:和为0最大和为0跨越中点的最大子数组和为5+0=5分治法求解最大子数组的时间复杂度算法的基本操作为加法和max操作。递推公式如下:其中T(n/2)为递归求解子数组的时间,Θ(n)为计算跨越最大子数组算法的时间复杂度。根据主定理,T(n)∈Θ(nlogn)。与枚举法的Θ(n³)相比,分治法大大提高了求解效率。分治法的灵活设计这个案例说明,分治法的三个步骤需要根据不同的情况进行相应的设计:分解过程可以根据数据的规模将问题一分为二,或者按照特定策略对数据进行划分解决过程可以使用显式的栈来优化求解过程;当数据规模较小时,也可以放弃递归改用迭代合并过程子问题的解在合并时,可能需要进行额外的操作才能得到原问题的解进阶:大整数相乘当整数的位数增加到几十位甚至上百位时,传统的逐位相乘方法会变得非常缓慢。大整数乘法问题就是要设计一种高效的算法,快速计算两个大整数的乘积。对于两个n位整数X和Y,传统的逐位相乘方法需要n²次单独的乘法操作,时间复杂度为Θ(n²)。分治法求解大整数相乘对于n位的大整数X和Y,按如下方式进行分解:其中a和c代表X和Y的高位部分(前n/2位),b和d代表X和Y的低位部分(后n/2位)。X×Y的乘积可转为:原问题分解为四个子问题:ac、ad、bc和bd。简单分治法的性能此算法需要的乘法次数M(n)的递推公式如下:求解此递推公式可得M(n)=n²。与逐位乘法的方法相比,此分治算法需要的乘法比较次数仍为n²,并未有提升。这说明初始的分治方案可能未必能显著提升效率,需要进一步优化。Karatsuba算法Karatsuba优化了上述分治策略,通过减少子问题的规模来提升效率:通过这一变换,原本计算P₂需要求解ad和bc两个子问题,现减少为一个子问题。

观察：通过减少子问题的规模,大整数乘法显著提升了效率。Toom-Cook算法Toom-Cook算法是一种用于大整数乘法的递归分治算法,通过将大整数分割成更小的部分,降低乘法运算的复杂度。Toom-3算法将每个大整数分割成3个部分,利用多项式的运算思想进行乘法计算:划分数位:将A和B分别划分为3个相等长度的部分构建多项式:将A和B表示为以基数X为底的多项式评估点计算:选择若干个不同的点,计算在这些点上多项式的值插值求解:根据已知的值,求出乘积多项式的系数结果合成:将乘积多项式转换回十进制表示Toom-3算法示例:划分与构建以A=123456,B=789012为例,使用Toom-3算法计算它们的乘积。步骤1:划分数位将A和B分成3个部分,每部分包含2位数字(基数X=100):A₂=12,A₁=34,A₀=56B₂=78,B₁=90,B₀=12步骤2:构建多项式构建多项式A(x)和B(x):A(x)=12x²+34x+56B(x)=78x²+90x+12Toom-3算法示例:评估点计算选择评估点x=0,1,-1,-2,∞,计算对应的值:x=0P₀=56×12=672x=1P₁=102×180=18,360x=-1P₋₁=34×0=0x=-2P₋₂=36×144=5,184x=∞P∞=12×78=936Toom-3算法示例:插值与合成设乘积多项式为C(x)=c₄x⁴+c₃x³+c₂x²+c₁x+c₀。根据已知的评估点,建立方程组并求解:c₄=936c₃=3,732c₂=7,572c₁=5,448c₀=672将系数组合回十进制表示(基数X=100):结果=936×100⁴+3,732×100³+7,572×100²+5,448×100+672=97,408,265,472Toom-3算法的性能分析

Θ(n²)传统竖式乘法Θ(n^1.59)Karatsuba算法Θ(n^1.46)Toom-3算法Toom-Cook算法的设计思想Toom-Cook算法的设计思想基于分治策略和多项式插值。通过将大整数看作多项式的系数,将整数乘法转化为多项式乘法,再通过在特定点的评估和插值,减少乘法运算的次数,提高计算效率。如果Toom-Cook算法继续扩展到更高阶的形式,例如Toom-4或Toom-5,则可以通过进一步的分治策略将大整数乘法转化为更多较小整数的乘法,但代价是增加了加法和减法的复杂度。进阶:矩阵乘法人工智能深度学习模型运算的一个基本操作是矩阵乘法。考虑A和B两个2×2的矩阵,计算矩阵C=AB。按照矩阵运算的定义,矩阵C中的每个元素需要A的某一行和B的某一列进行点积运算。因此,共需要8次乘法操作。当A和B扩展为n×n的矩阵时,计算矩阵C需要的乘法次数为n³。分治法求解矩阵乘法将矩阵A分解为A₁₁、A₁₂、A₂₁和A₂₂四个n/2×n/2的矩阵,同理,矩阵B可按照同样方式分解。矩阵C=AB也可以分解为四个n/2×n/2的子矩阵:C₁₁=A₁₁B₁₁+A₁₂B₂₁C₁₂=A₁₁B₁₂+A₁₂B₂₂C₂₁=A₂₁B₁₁+A₂₂B₂₁C₂₂=A₂₁B₁₂+A₂₂B₂₂计算矩阵C需要进行8次子矩阵的乘法运算。递推公式为M(n)=8M(n/2),求解可得M(n)=n³∈Θ(n³)。Strassen算法在1969年,Strassen提出了一个革命性的矩阵乘法算法,该算法成功地将8个子问题减少为7个,从而显著降低了计算复杂度。Strassen算法定义以下7个中间矩阵:M₁=(A₁₁+A₂₂)(B₁₁+B₂₂)M₂=(A₂₁+A₂₂)B₁₁M₃=A₁₁(B₁₂-B₂₂)M₄=A₂₂(B₂₁-B₁₁)M₅=(A₁₁+A₁₂)B₂₂M₆=(A₂₁-A₁₁)(B₁₁+B₁₂)M₇=(A₁₂-A₂₂)(B₂₁+B₂₂)Strassen算法的子矩阵计算利用7个中间矩阵,可以计算矩阵C的4个子矩阵:C₁₁M₁+M₄-M₅+M₇C₁₂M₃+M₅C₂₁M₂+M₄C₂₂M₁-M₂+M₃+M₆通过这种分解方法,只需要计算7个中间矩阵,而计算每个中间矩阵仅需要求解一个子问题。Strassen算法的性能分析递推公式为M(n)=7M(n/2),求解可得:

计算效率有显著的提升。但是,上述子问题分解方式将求解8个子问题减少为7个,也引入了18次的矩阵加减法开销。

分治法的核心设计思想从上述分析中,我们可以总结分治法中的两个核心设计和改进思想:减少子问题的规模Strassen算法成功地通过数学关系巧妙地将8个子问题减少为7个,这一改进是降低时间复杂度的根本原因。分治法的效率提升依赖于在递归过程中减少递归的次数或子问题的规模。平衡算法的各部分开销尽管Strassen算法减少了乘法次数,但引入了矩阵加减法的额外开销。然而,这些额外开销在总体复杂度中仍然能够与乘法次数的降低相协调,最终实现了时间复杂度的整体下降。Strassen算法的实际应用

在现代计算中,比如深度神