《算法设计与分析》课件 第1-4章 算法基础 -动态规划

算法基础算法在计算机科学中占据核心地位,是解决各种复杂问题的基石。它不仅决定了程序的执行效率和资源利用率,还影响着软件系统的性能和可扩展性。从数据处理、人工智能到网络安全,几乎所有计算机应用都依赖高效的算法来实现功能和优化性能。本章将介绍算法的含义以及算法分析与设计的一般性框架。第一部分算法的含义什么是算法?算法是一种解决问题的方法或步骤,就像做事情的说明书,告诉你如何逐步完成一件事。做饭的例子假设当前需要解决的问题是做一顿饭,那么菜谱就是算法。它告诉你需要哪些食材,以及按照什么顺序和步骤去烹饪,最终做出一道或多道菜。查找电话号码问题是找电话号码簿中的某个名字对应的电话号码。那么算法可以设计成从第一页开始逐个查找,直到找到为止;或者直接翻到中间,看看名字位于哪一半,再继续对半查找。算法的特点输入和输出算法通常需要明确的输入和输出。输入是指需要解决的问题所依赖的数据或信息,输出则是算法处理后的结果或答案。明确性算法的每一步必须是明确且可执行的指令。比如"加盐少许"不够明确,应该具体化为"加盐3克"。多样性对于同一个问题,可能存在多种不同的算法。这些算法在执行效率、资源消耗等方面可能存在显著差异。有穷性算法必须在有限的步骤内结束,确保问题能够被解决。如果算法不能在有限的步骤内完成,就无法得到结果。输入和输出的详细说明算法通常需要明确的输入和输出。输入是指需要解决的问题所依赖的数据或信息,输出则是算法处理后的结果或答案。做饭问题输入:各种食材输出:一道或多道完成的菜肴电话簿查找问题输入:电话簿和要查找的名字输出:该名字对应的电话号码明确性的重要性算法的每一步必须是明确且可执行的指令。比如,在做饭的问题中,如果其中一个步骤是"加盐少许",不同的人可能对"少许"有不同的理解,有些人认为是1克,有些人可能认为是5克。这种不明确性会导致每次执行的结果可能不同。为了消除歧义,可以将"加盐少许"具体化为"加盐3克",这样指令就明确给出了具体的量,任何人或计算机都可以按照这个要求准确执行操作。多样性:不同的解决方案对于同一个问题,可能存在多种不同的算法。这些算法在执行效率、资源消耗等方面可能存在显著差异。逐页查找从第一页开始逐个查找,效率较低,尤其当电话号码簿很大时二分查找通过每次将查找范围减半的方法,能够大幅提升查找效率,快速定位目标有穷性:算法必须终止算法必须在有限的步骤内结束,确保问题能够被解决。如果算法不能在有限的步骤内完成,就无法得到结果,相当于未能解决问题。反例比如在做饭的问题中,如果算法中的一个指令是"反复洗菜",且没有明确的结束条件,那么该算法将无限执行下去,无法完成做菜的目标。因此,设计算法时必须确保每个可能的执行路径都能在有限的步骤内结束。案例:找出最大值我们希望设计一个算法,找出一组数字(例如[4,7,1,9])中的最大值。现有一种算法,通过逐一比较数字,最终找到最大值。算法的主要步骤01初始化假设第一个数字是最大值,记为max02逐一比较从第二个数字开始,依次查看剩下的每个数字。如果当前数字比max更大,就将max替换为当前数字03结束判断当所有数字都被检查后,max就是这组数字的最大值算法执行过程模拟下面我们手动模拟一下算法的执行过程:初始化max初始化为4比较7和max7>4,更新max为7比较1和max1<7,max不更新比较9和max9>7,更新max为9结束判断所有数字遍历完毕,算法结束,最大值为9[4,7,1,9]算法特性验证上述算法有明确的输入(数字列表)和输出(最大值)。明确性算法的每一步操作都清晰、无歧义,例如"比较数字大小"和"更新最大值"是具体可执行的步骤有穷性算法会在有限的步骤内完成,因为它只需要遍历整个数字列表一次正确性算法能够正确找出数字列表中的最大值描述算法的三种方式描述算法时,我们通常有自然语言描述、编程语言和伪代码这三种方式。自然语言描述优点:易于理解缺点:对复杂算法可能显得冗长且不够直观编程语言实现优点:可以直接运行并验证算法的正确性缺点:对初学者可能增加理解难度伪代码描述优点:既无需严格遵循某种编程语言的语法规则,又能清晰地展现算法的核心步骤和思想适用:非常适合初学者和跨学科读者使用编程语言实现示例使用高级编程语言将算法转化为可运行的代码:deffind_max(numbers):max_val=numbers[0]fornuminnumbers[1:]:ifnum>max_val:max_val=numreturnmax_valprint(find_max([4,7,1,9]))它的优点是可以直接运行并验证算法的正确性,但是对初学者可能增加理解难度。伪代码描述伪代码以接近自然语言的方式表达算法逻辑,既无需严格遵循某种编程语言的语法规则,又能清晰地展现算法的核心步骤和思想,便于转化为编程语言实现。算法:求解一组数字中最大值输入:numbers[]为一组数字,n表示数字的数量输出:最大值的大小max←numbers[1]//max初始化为第一个数fori←2tondo

ifnumbers[i]>maxthen

max←numbers[i]//如果当前数字更大,则更新maxreturnmax为什么选择伪代码?在本书中,我们选择使用伪代码的形式来描述算法。对于简单算法自然语言足以表达其逻辑对于复杂算法伪代码和编程语言可以更高效地描述和实现其逻辑考虑到使用特定编程语言描述算法可能要求学生对该语言有一定的理解和熟悉度,这可能对初学者形成额外的学习门槛,因此,本书最终选择了使用伪代码的形式来描述算法。第二部分算法分析框架算法分析框架对于同一个问题,不同的算法可能有不同的执行效率。而算法的效率通常指时间效率和空间效率。时间效率(时间复杂度)描述的是算法运行的快慢空间效率(空间复杂度)关注的是算法所需的额外空间随着存储技术的发展,计算机的存储容量已大幅提升,算法所需的额外空间不再是我们重点关注的问题。因此,在本书中,我们更多地分析算法的时间效率。2.1时间复杂度多项式求值问题我们以多项式求值问题介绍算法时间复杂度的分析框架。假设有一个n次多项式:

多项式求值算法伪代码算法:多项式求值输入:coefficients[]为系数列表(假设a₀保存在下标为0的位置),n为多项式的阶数,x为变量输出:result为多项式的值result←0//初始化结果为0current_power←1//初始化x⁰=1fori←0tondo

result←result+coefficients[i]*current_power//累加当前项的值

returnresult算法时间效率分析下面我们分析多项式求值算法的时间效率:第一行将变量result初始化为0,只需要一次操作,是一个简单的赋值操作,耗时固定第二行将current_power初始化为1,也是一个简单的赋值操作,同样耗时固定第三行循环是算法中重复执行的部分。这段代码会从i=0一直执行到i=n,每次循环需要完成循环体内的指令。第四行在每次循环中,这行代码会执行两件事:将当前系数(aᵢ)和xⁱ相乘,这是一次乘法操作;把乘积加到result上,这是一次加法操作。由于循环执行n+1次,那么乘法和加法操作都执行n+1次第五行这行代码在每次循环中更新xⁱ的值,只需要一次乘法操作。循环执行n+1次,总共会执行n+1次乘法操作第六行返回计算结果result只需要一次简单的操作,耗时固定关键发现可以看出,算法中初始化和返回结果的操作是固定的,它们只需要执行少量的赋值和返回操作,其耗时不会随多项式的阶数n的增加而增加。而循环部分的操作次数是算法效率的关键,因为循环中的每一步都需要重复执行多次计算操作,且次数随着多项式的阶数n的增加而增加。在每次循环中,算法需要执行两次乘法操作(第四行的计算系数乘以当前幂和第五行的更新下一次幂值)以及一次加法操作(第四行的累加当前项的值)。对于输入规模为n的情况下,循环会执行n+1次,因此总共执行了2(n+1)次乘法操作和n+1次加法操作。基本操作计数法也就是说,算法的整体执行时间可以近似看作是一次乘法和一次加法的执行时间,分别乘以对应的执行次数之和。由于在计算机中,乘法和加法的执行时间是固定的,并且相差不大,我们可以用乘法和加法的执行次数来估计算法的运行效率。这种计数方式为我们提供了分析时间复杂度的一种标准化方法。通过统计算法中某些操作的执行次数,我们可以从宏观上评估算法的效率。这种方法的好处在于,它不依赖具体的硬件环境(如CPU的速度或内存的大小),而是专注于算法本身的性质。基本操作的概念为了更方便地分析各种算法,忽略具体的操作类型(如乘法或加法),而是将它们抽象为一种"基本操作"。什么是基本操作?基本操作是指算法中最常执行、对效率影响最大的操作,在本例中是乘法和加法为什么统计基本操作?统计基本操作的执行次数,可以直观地描述算法的运行效率。当输入规模逐渐增大时,基本操作的执行次数随输入规模的变化趋势成为衡量算法效率的核心指标例如:当前算法的基本操作次数与输入规模成正比(如3(n+1)),说明它的效率增长是线性的。算法时间复杂度分析步骤综上所述,算法时间复杂度的分析步骤总结如下:01确定问题输入规模n的含义输入规模n是问题的一个核心属性,用来衡量输入数据的大小或复杂程度。它直接影响算法执行的操作次数02确定算法的基本操作基本操作是算法中最核心、最频繁执行的操作,直接决定了算法的执行时间03确定基本操作的执行次数需要逐步分析算法的各个部分,确定基本操作在不同环节中被执行的次数,并将其累计求和分析找最大值算法我们按照上述步骤分析找最大值算法:1确定问题输入规模n的含义输入规模是数组的长度n,算法的执行时间与数组的长度n密切相关2确定算法的基本操作在循环中存在比较操作和赋值操作。从操作的复杂性来看,比较操作更耗时且对算法性能影响更大。而赋值操作仅在比较结果为真时执行,其具体次数取决于数据分布。因此,比较操作被选为算法的基本操作3确定基本操作的执行次数循环体执行n-1次(i从2到n),因此比较操作共执行n-1次因此,随着输入规模n的增大,算法需要执行的基本操作次数也线性增长,这表明算法的运行效率与n成正比。基本操作次数的影响因素在上述多项式求值和求解数组中最大值问题中,基本操作的执行次数仅仅与输入数据的规模相关。那么其是否有可能还取决于输入数据的其他属性,比如数据的分布?考虑在一组数字中搜索给定值key的问题。该算法从数组的第一个元素开始,依次比较数组numbers中的每一个元素。如果发现当前元素与key相同,则将其在数组中的下标记录到pos中,并结束循环。搜索算法伪代码算法:在数组中搜索给定key输入:numbers[]为一组数字,n表示数字的数量,key为要搜索的数字输出:pos为key所在的位置,若未找到则为-1pos←-1//初始化位置为-1,表示未找到fori←1tondo

ifnumbers[i]==keythen

pos←i//找到key,更新位置

break//提前退出循环returnpos搜索算法的时间复杂度分析下面我们尝试用之前总结的步骤去分析此算法的时间复杂度:第一步:确定问题输入规模n的含义问题的输入规模是数组的长度n第二步:确定算法的基本操作算法的基本操作为第三行的比较操作,因为它在循环中被反复执行,是决定算法时间复杂度的关键因素第三步:确定基本操作的执行次数如果numbers[1]与key相等,则算法在第一次比较后退出循环,比较操作仅执行一次。如果key等于numbers[n],则算法需要执行n次比较操作才能找到目标值。如果数组中不存在与key相同的元素,算法需要执行n次比较操作最坏、最好和平均情况从这个例子可以看出,基本操作的执行次数不仅与输入规模相关,还与输入数据的取值相关。在这种情况下,需要分别研究最坏情况、最好情况和平均情况下基本操作的执行次数。最坏情况输入数据的属性使算法执行最多次基本操作的情况。最坏情况分析保证了我们对算法性能的最保守估计,用于评估在最差条件下的表现最好情况输入数据属性使算法执行最少次基本操作的情况。最好情况分析展示了算法在最理想条件下的性能表现平均情况所有可能输入的基本操作次数的期望值。平均情况分析反映了算法在实际使用中最常见的表现。要分析平均情况下基本操作的执行次数,通常需要对输入数据做出一定的假设,例如假设数据服从某种概率分布平均情况分析示例以搜索算法为例,假设待查找的值key在数组中的每个位置被找到是等概率的(不考虑查找失败的情况)。具体来说:数组第1个位置找到key的概率为1/n,此时基本操作执行了1次数组第2个位置找到key的概率也为1/n,此时基本操作执行了2次数组第i个位置找到key的概率为1/n,此时基本操作执行了i次因此,基本操作执行次数的期望值可以通过以下公式计算:修正后的分析步骤基于以上讨论,基本操作的执行次数同时取决于问题输入规模和输入的取值,将其考虑在内,算法时间复杂度的分析步骤可修正如下:01确定问题输入规模n的含义02确定算法的基本操作03确定基本操作的执行次数3.1:检查基本操作的执行次数是否仅取决于输入规模n,如果是,那么只需统计基本操作随n变化的次数即可3.2:如果基本操作的执行次数还取决于输入数组的取值,则需要分别研究最坏情况、平均情况和最好情况的执行次数2.2递推公式求解递推公式求解在前面的小节中,我们主要通过分析"循环体中基本操作的执行次数"来推断算法的时间复杂度。然而,当算法采用递归方式实现时,仅仅数循环往往不够直观。这时,我们需要用到"递推公式"的方法来分析算法的效率。我们以计算阶乘为例,展示如何使用递推公式分析算法的时间复杂度。阶乘函数定义阶乘函数的定义如下:计算阶乘的递归算法算法:计算阶乘输入:n为一个非负整数输出:F(n)为n的阶乘F(n):

ifn==0then

return1//递归出口，0的阶乘定义为1

else

returnn*F(n-1)//递归计算阶乘阶乘算法的时间复杂度分析下面我们分析此算法的时间复杂度:1确定输入规模在计算阶乘的问题中,输入规模就是非负整数n本身。算法的执行时间将随着n的增大而增大2确定基本操作观察算法的伪代码,计算阶乘的递归算法中,最核心、最频繁执行的操作是乘法操作。具体来说,在每次递归调用中,当n>0时,都需要将当前的n与F(n−1)相乘。因此,我们将乘法操作视为算法的基本操作3建立递推公式令M(n)表示计算F(n)所需的基本操作(乘法)的次数。当n=0时,算法直接返回1,不进行乘法操作。因此,M(0)=0。当n>0时,算法执行一次乘法操作,并递归调用F(n−1)。而求解F(n-1)需要的基本操作的次数为M(n-1)递推公式由此,可得如下递推公式:我们采用代入法求解上述递推公式。代入法求解递推公式M(n)=M(n-1)+1=(M(n-2)+1)+1//M(n-2)+1替换M(n-1)=M(n-2)+2=(M(n-3)+1)+2//M(n-3)+1替换M(n-2)=M(n-3)+3⋮=M(n-n)+n×1//一直替换,直到M(0)=0+n=n通过递推公式的求解,我们得到计算阶乘的递归算法中,基本操作的执行次数为M(n)=n。这意味着,算法的时间复杂度与输入规模n成线性关系。二分查找问题下面考虑一个更为复杂的例子二分查找。二分查找常用于在有序数组中快速查找目标值,它每次将搜索范围缩小一半,因此搜索速度比线性查找更快。二分查找算法伪代码算法:二分查找输入:numbers[]为一个有序数组,已按升序排序,n表示数组的长度,key为待查找的数字输出:pos为key所在的位置,若未找到则为-1binary_search(numbers,low,high,key)

iflow>highthen

return-1//若区间无效,返回-1

mid←⌊(low+high)/2⌋//计算中间位置

//与中值比较

ifnumbers[mid]==keythen

returnmid

elseifnumbers[mid]<keythen

returnbinary_search(numbers,mid+1,high,key)//在mid右边搜索

else

returnbinary_search(numbers,low,mid-1,key)//在mid左边搜索pos←binary_search(numbers,1,n,key)//调用binary_searchreturnpos二分查找的时间复杂度分析在二分查找算法中,每次递归都会把搜索区间缩小一半,并在新的区间中继续查找。1确定输入规模此算法问题的输入规模就是数组的长度n。当n越大,算法的搜索区间就越大,耗时越长2确定基本操作观察伪代码会发现每次递归调用中,都要比较low和high的值(第一行),计算mid的值(第三行)和比较numbers[mid]和key的大小。其中,比较numbers[mid]和key的大小被视为基本操作,因为它决定了算法的搜索方向,甚至决定是否结束搜索。而其他操作通常被视为"固定常数"开销3分析最坏情况基本操作的执行次数不仅取决于问题规模,还取决于输入数据的分布。最好情况发生在第一次比较就找到key,即key正好为numbers的中值,此时基本操作只执行1次比较即可返回结果。最坏情况下,每次比较都无法直接找到key,并且算法会将搜索区间从n逐步缩小到1才返回结果(要么在最后一刻找到,要么确实不存在)二分查找的递推公式记C(n)为当搜索区间长度为n时,最坏情况下比较操作执行的次数。根据算法逻辑,在进行一次比较后,问题规模从n变为n/2(忽略取整),则我们可以用如下递推公式来表达C(n):求解二分查找的递推公式为了求解该公式,下面我们使用代入法进行推导:

所以,最坏情况下的基本操作执行次数约为1+log₂n。分析平均情况下比较操作的执行次数略复杂,这里不做详细介绍。求解递推公式的通用步骤1列出递推关系根据算法的递归结构,表达基本操作的执行次数T(n)与更小规模的T(k)之间的关系,写出递推公式2确定基准条件明确递推的终止条件,通常是最小规模问题的解决方式3选择求解方法常用的方法包括代入法、递归树法、主定理和生成函数4求解递推公式通过所选择的求解方法,求解出T(n)的值适用于递归算法的分析步骤结合上述求解递推公式的通用步骤,算法时间复杂度的分析步骤可修正如下,使其适用于递归算法:01确定问题输入规模n的含义02确定算法的基本操作03确定基本操作的执行次数3.1:检查基本操作的执行次数是否仅取决于输入规模n,如果是,那么只需统计基本操作随n变化的次数即可3.2:如果基本操作的执行次数还取决于输入数组的取值,则需要分别研究最坏情况、平均情况和最好情况的效率3.3:根据算法类型选择分析方法。对于非递归算法,可以通过直接的求和公式计算基本操作的执行次数。对于递归算法,需要建立并求解递推公式来描述基本操作的执行次数2.3渐进复杂度渐进复杂度在上一节中,我们通过精确统计基本操作的执行次数,揭示了算法执行时间如何随着输入规模n的增加而变化。需要特别注意的是,在算法分析中,我们主要关注的是算法运行时间随输入规模增大的增长趋势,而不仅仅是具体的操作次数。这种增长趋势能够帮助我们评估算法在处理大规模数据时的性能表现,从而为算法的优化与选择提供理论依据。常数项和常数因子的影响为了更直观地理解算法的运行时间如何随n的增大而变化,我们先来看一个示例。假设某算法的基本操作执行次数是T(n)=3n+2。通常将2称为常数项,因为它与n的大小无关,不会随输入规模的变化而变化。通常称3是乘在n上的常数因子,因为它是与可变量n相乘的一个常数系数。当输入规模从n提高到2n时,算法的基本操作的执行次数变为T(2n)=6n+2。此时,输入规模翻了一倍,但基本操作的执行次数并没有正好翻倍,因为存在常数项。执行次数比值分析若我们考察算法在规模为2n和规模为n时,基本操作的执行次数的比值:当n较大时,分子和分母中常数2的影响逐渐变得微乎其微。设想n趋于无穷大,该比值近似为:

忽略常数因子假设我们仅关注3n,即T(n)=3n,当输入规模从n提高到2n时,基本操作的执行次数之比为:当输入规模从n提高到4n时,基本操作的执行次数之比为:可见,常数因子3仅起到缩放作用,在计算执行次数之比时可以约掉,即它与n的真正增长趋势无关。渐进符号算法分析中通常使用渐进符号来更好地描述在输入规模n逐渐增大的情况下算法运行时间的增长趋势。我们介绍三种常用的渐进符号:O:上界表示算法执行时间不会比某个函数的增长速度更快太多Ω:下界表示算法执行时间不会比某个函数的增长速度更慢太多Θ:紧确界表示算法执行时间与某个函数的增长速度处在同一数量级O符号示例非正式来讲,O(g(n))是增长速度小于等于g(n)的函数集合。下面给出几个例子:正确的例子n∈O(n²)3n+1∈O(n)n(n-1)/2∈O(n²)错误的例子n²+n∉O(n)0.00001n²∉O(n)n⁴+n³∉O(n³)我们已知常见的函数增长速度关系为:1<logn<n<nlogn<n²<n³<2ⁿ<n!Ω和Θ符号示例Ω(g(n)):增长速度大于等于g(n)的函数集合正确的例子:n²∈Ω(n)3n+1∈Ω(n)n³∈Ω(n²)错误的例子:nlogn∉Ω(n²)0.00001n²∉Ω(n³)n⁴+n³∉Ω(n⁵)Θ(g(n)):增长速度等于g(n)的函数集合例子:3n+2∈Θ(n)3n²+2n+1∈Θ(n²)nlogn+3n+2∈Θ(nlogn)使用极限比较增长速度

极限方法示例

使用渐进符号的分析步骤结合上述内容,算法时间复杂度分析关注的是随着输入规模的增加,算法执行时间的增长趋势,通常使用渐进符号来忽略基本操作执行次数中的常数项、常数因子和低阶项。当我们使用渐进复杂度来描述算法的时间效率时,算法时间复杂度分析步骤如下:01确定问题输入规模n的含义02确定算法的基本操作03确定基本操作的执行次数04使用渐进符号表示基本操作的执行次数第三部分算法设计框架算法设计框架算法设计是计算机科学的核心。本节介绍算法设计的基本框架，帮助理解设计算法的常用策略和思维方式。01分析问题理解输入、输出、约束条件和边界情况02选择策略根据问题特点选择合适的设计策略03设计算法用伪代码描述算法步骤，确保逻辑清晰04验证正确性通过数学证明或测试验证算法正确性05分析复杂度评估时间和空间复杂度，判断性能06编码实现转换为实际代码并针对性能优化问题分析：数据与特性数据层面明确输入数据格式和目标输出分析数据规模大小（如数百万级输入需要更高效的算法）关注极端情况：空输入、单元素、零顶点等识别特殊情形对算法实现的影响问题特性最优子结构：问题可分解为子问题重叠子问题：子问题重复出现贪心选择性质：局部最优导致全局最优根据特性选择分治、动态规划或贪心算法深入理解问题的数据规模和内在特性，是选择正确算法策略的关键。算法设计策略分治法问题可拆分并递归处理动态规划具备重叠子问题与最优子结构贪心算法局部决策保证全局最优，优雅高效回溯与分支限界需要穷举搜索但存在剪枝条件近似算法有限时间内寻求近似解选择策略后，需确定算法流程、数据结构，用伪代码描述步骤，并考虑边界情况。在小规模示例上手动推演，可快速检测漏洞和优化空间。随机算法引入随机性并行算法利用多处理器的并行计算能力枚举法逐一列出，逐一验证算法分析与实现正确性证明使用数学归纳法证明算法在所有合法输入下产出正确结果复杂度分析评估时间和空间复杂度，判断是否满足实际需求代码实现选择编程语言，确定数据结构，处理边界情况和异常输入测试优化设计多组测试用例，考虑并行加速提高执行效率关键提示：如果算法效率不满足需求，需要改进或重新设计。大规模数据可考虑并行加速。枚举法算法设计的起点与基础什么是枚举法?枚举法,也称为蛮力法,是一种根据问题本身的性质和定义,逐一列举出所有可能的解,并在列举过程中逐一检验每个可能解是否为问题的真正解的方法。如果某个解满足条件,则采纳该解;否则,忽略它。尽管这种方法不一定是最快的,但它保证能够找到最优解,因此枚举法是我们学习算法的起点。生活中的枚举法假设一个袋子中装有许多大小不同的球,现在需要找出其中最大的一个球。我们可以逐一取出球进行比较,直到找到最大的那个球。这就是枚举法的基本思路:列出所有可能的解,然后逐一验证每个解是否满足条件。寻找最大球算法枚举法的优势与局限优势能够全面遍历整个搜索空间,从而确保最终得到最优解局限需要检查所有可能的解,效率往往较低,尤其是在解空间规模较大时应用场景适合小规模问题或作为算法学习的起点,通常需要结合其他优化方法枚举法求解范式01确定枚举对象枚举对象定义了问题解的整个搜索空间02逐一列举可能解根据枚举对象的性质,逐一列举每一种可能的情况03逐一验证可能解根据问题的要求,逐一验证枚举对象的每一个取值是否满足条件中国剩余定理《孙子算经》中记载:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?有一个数,它被3除的余数是2,它被5除的余数是3,被7除的余数是2,求这个数。用枚举法求解"有数几何"1确定枚举对象此问题的枚举对象为所有的正整数2逐一列举可能解通过循环的方式从1开始逐一遍历正整数,直到找到一个满足条件的正整数3逐一验证可能解如果正整数满足三个整除条件,则采纳它,算法结束枚举法的编程优势枚举法在求解问题时,除了能保证得到最优解,还有一个明显的优势是方便编程。只要根据问题描述确定搜索空间,然后在逐一验证时确定搜索条件,那么可容易解决问题。字符串匹配问题字符串匹配问题是计算机科学中的一个经典问题,有着广泛的实际应用。搜索引擎在网页中查找包含关键词的内容文本编辑器"查找和替换"功能DNA序列分析匹配特定的序列模式字符串匹配的目标在一个较长的文本字符串T中,寻找一个较短的模式字符串P出现的位置。如果能够找到这个位置,就说明模式字符串存在于文本中,否则就不存在。假设文本字符串为"helloworld",模式字符串为"world",字符串匹配问题就是要找到"world"在"helloworld"中的位置,也就是文本字符串的第七个字符开始匹配成功。字符串匹配的枚举法求解确定枚举对象假设文本字符串T的长度为n,模式字符串P的长度为m(n≥m),则P在T中出现的位置可能有n-m+1个逐一列举可能解通过循环的方式逐一遍历可能的匹配位置,从位置1开始,直到n-m+1逐一验证可能解如果模式字符串中的每一个字符都与文本字符串对应位置的字符相等,就认为匹配成功字符串匹配算法复杂度Θ(nm)最坏情况需要检查文本字符串T中的所有可能匹配位置,每个位置上都要比较模式字符串P的所有字符Θ(m)最好情况模式字符串P在文本字符串T的第一个位置就成功匹配O(1)空间复杂度仅需常数级别的额外空间来存储变量旅行商问题(TSP)TSP是一个经典的组合优化问题,目标是找到一条最短路径,使得旅行商从一个城市出发,访问每个城市恰好一次,并最终返回起始城市。4城市TSP问题示例对于每个城市，都有一条路径去往其他3个城市，而城市之间的路径为正整数。

A→B→C→D→A,距离:23A→B→D→C→A,距离:23A→C→B→D→A,距离:14A→C→D→B→A,距离:23A→D→B→C→A,距离:14A→D→C→B→A,距离:23从城市A出发再返回A的最短路径是:(A,C,B,D,A)和(A,D,B,C,A)第二步：逐一验证可能解起始城市为A时,共有6条路线。当起始城市为B、C或D时,各有6条路线。当有4个城市时,路线总数量为24条。TSP枚举法的时间复杂度1010个城市路径数量为10!=3,628,8002020个城市路径数量超过2×10¹⁸虽然枚举法能够保证找到TSP的最优解,但它需要遍历所有n!条可能的路径,时间复杂度为O(n!)。随着城市数量n的增加,算法的运行时间呈阶乘级增长,使得枚举法在解决大规模TSP问题时变得不切实际。O(n!)背包问题在某地发生地震后,一架运输机需要将一些物资送往灾区。运输机的最大承重为W,每个物品的重量和紧急程度分别为w₁,w₂,...,wₙ和v₁,v₂,...,vₙ,其中n是物品的数量。目标是从这些物品中选择一部分放入运输机,使得运输机的总重量不超过W,同时让运输机带去的物资能满足灾区人民的急迫需求。背包问题示例假设运输机的最大承重是W=10,现有4件物资:食物2中(3)水3高(5)帐篷4低(1)药品5高(5)物品

重量紧急程度背包问题的枚举法求解确定枚举对象枚举对象是所有物品的选择组合。对于每个物品,可以选择放入运输机或者不放入,所以每个物品有两种选择。对于4个物品,则总共有2⁴=16种可能的物品组合逐一列举可能解对于每个可能的物品组合,可以使用二进制数(a₁,a₂,a₃,a₄)来表示,aᵢ=1表示选择第i个物品,aᵢ=0表示不选择第i个物品逐一验证可能解对于每一个可能的物品组合,验证其总重量是否超过背包的承重限制。如果超过,则忽略这个组合;如果不超过,则计算该组合的总紧急程度背包问题最优解最优组合:1101(二进制)选择:食物+水+药品总重量:10总紧急程度:13(最大值)因此,算法时间复杂度为Θ(n·2ⁿ),当n较大时,算法的运行时间将迅速增加。在后续章节,我们会用贪心算法、动态规划等思想再次分析此问题并给出更高效的算法。外层循环遍历每一种物品组合(共2ⁿ种),随后调用calculateWeightAndUrgency函数计算当前物品组合下的物体总重量和总紧急程度(循环体需要执行n次)。n皇后问题在一个n×n的棋盘上,摆放n个皇后使得任意的两个皇后不在同一行、同一列和同一对角线上,问有多少种不同的摆放方法。我们考虑一个4×4的棋盘来理解这个问题。

4皇后问题的枚举法求解1确定枚举对象枚举对象是4个皇后的摆放位置,用(p₁,p₂,p₃,p₄)表示,其中pᵢ表示第i个皇后在棋盘中的列位置2逐一列举可能解假定每一行只放一个皇后,且各皇后不在同一列,则4个皇后的组合为4×3×2×1=24种3逐一验证可能解对于每一种可能的摆放组合,需要验证其是否符合4皇后问题的要求,只需检查两个皇后是否处于同一条对角线遍历n!种摆放方式isValid需要两两比较,最坏情况下时间复杂度为Θ(n²)枚举法求解n皇后问题的时间复杂度至少为Ω(n!),组合算法概述TSP问题和n皇后问题涉及到排列生成问题。目前已有多种方法可生成给定集合的所有排列,下面介绍几种经典的排列生成算法。自底向上的排列生成对于生成{1,...,n}的所有n!个排列,假设已知{1,...,n-1}的所有(n-1)!个排列,那么如何得到{1,...,n}的所有排列?我们可以通过将n插入到这些排列中的不同位置来得到{1,...,n}的所有排列。排列生成示例假设已知{1,2,3}的所有排列为:1,2,3;1,3,2;2,1,3;2,3,1;3,1,2;3,2,1将元素4插入到每个排列中的每个位置,得到{1,2,3,4}的所有排列。例如,对于排列1,2,3,可以生成:4,1,2,3(插入位置1)1,4,2,3(插入位置2)1,2,4,3(插入位置3)1,2,3,4(插入位置4)同理，要得到{1,2,3}的所有排列，可以将数字3插入到{1,2}的每个排列中的所有可插入位置。自底向上排列生成的复杂度在第i次迭代时,会遍历perms中所有长度为i-1的排列(此时perms中已包含(i-1)!个这类排列),每个排列有i个可插入位置。算法的时间复杂度为Θ(n!),空间复杂度为Θ(n·n!)。按字典序的排列生成

例如,对于{1,2,3,4},按照字典序它的所有排列为:1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321字典序排列生成算法步骤字典序算法复杂度O(n·n!)时间复杂度每次迭代生成排列时,最坏情况下为O(n),共有n!种排列O(1)空间复杂度仅需要存储若干临时变量(j,l)等Heap's算法Heap's算法是一种生成给定数组所有排列的方法。它的核心思想是,除了第一个排列外,每一个排列都是通过交换前一个排列中的两个元素得到的,从而生成不同的排列。Heap's算法的递归方式1第一步固定最后一个元素为n,递归生成前n-1个元素的所有排列,共有(n-1)!种排列2第二步从前n-1个元素中选择一个数m₁与aₙ交换,递归生成前n-1个元素的所有排列3第三步从前n-1个元素中选择一个数m₂与m₁交换,递归生成前n-1个元素的所有排列4重复依次类推,直到生成以mₙ₋₁为最后一个元素的所有排列

Heap's算法的交换策略n是偶数时先选择第一个数,然后是第二个数,接着是第三个数,依此类推n是奇数时总是选择第一个数Heap's算法示例生成{1,2,3,4}所有排列的过程:先生成最后一个元素为4的6个排列,然后将4和1交换,再生成最后一个元素为1的6个排列,然后将1和2交换,再生成最后一个元素为2的6个排列,最后将2和3交换,生成最后一个元素为3的6个排列,共生成24个排列。Heap's算法复杂度算法的时间复杂度为O(n!)空间复杂度为O(1)。算法的基本操作为swap,假设S(n)表示生成n个元素的所有排列需要的swap操作的次数,则:枚举法在操作系统中的应用磁盘调度问题是操作系统中一个经典的调度问题,涉及如何有效地管理磁盘的读写请求以优化磁盘的性能。假设磁盘上的当前磁头位置H磁道,现有一组待处理的磁盘请求,表示为一个整数数组R={r₁,r₂,...,rₙ},其中每个rᵢ表示一个待访问的磁道号。磁盘调度的目标是确定磁头移动的顺序,以最小化总的寻道时间或寻道距离,从而提高磁盘的访问效率。磁盘调度问题的枚举法求解1确定枚举对象枚举对象是n个待访问磁道的所有可能排列。对于每一个排列,表示一种可能的磁头移动顺序2逐一列举可能解生成所有n!种可能的请求处理顺序3逐一验证可能解对于每一种排列,计算其对应的总寻道距离,并记录最小值及其对应的排列磁盘调度示例假设当前磁头位置H=50,请求序列R={10,22,20,2,40,6}。对于排列{10,22,20,2,40,6},总寻道距离为:|50-10|+|10-22|+|22-20|+|20-2|+|2-40|+|40-6|=144对于n个请求,排列的总数为n!。对每种方案,需要计算总的寻道距离,因此,枚举法求解磁盘调度算法的时间复杂度为Ω(n×n!)。磁盘调度的实际应用随着请求数量n的增加,算法的时间复杂度呈阶乘级增长,这意味着当n较大时,枚举法的计算量将变得极其庞大,导致其在实际应用中几乎不可行。实际操作系统中通常采用更高效的磁盘调度算法,如SCAN算法、C-SCAN算法等。枚举法总结枚举法就是按照问题本身的性质,一一列举出该问题所有可能的解,并在列举的过程中,逐一检验每个可能解是否是问题的真正解。若是则采纳这个解;否则,忽略它。枚举法的主要特点实现简单算法逻辑清晰,易于理解和编程实现效率较低需要遍历所有可能的解,时间复杂度通常较高优化空间大通过剪枝等技术可以显著提升执行效率枚举法设计范式确定枚举对象枚举对象可以理解为问题解的表达形式,一般可以若干参数(p₁,p₂,...,pₙ)来表示。参数数目越少,问题解的搜索空间越小逐一列举可能解根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况逐一验证可能解根据问题的要求,一一验证枚举对象表达式的每一个取值,如果满足条件,则采纳它;否则,抛弃枚举法的适用场景小规模问题当问题规模较小时,枚举法可以快速得到最优解算法学习作为算法学习的起点,帮助理解问题的本质验证其他算法可以用枚举法验证其他优化算法的正确性分治法算法设计的核心思想从运动会组织说起在组织全校运动会时,可以将复杂工作分解为几个主要部分:体育项目安排、场地布置、奖品准备、宣传和报名等。每个部分由专门小组负责,各小组独立工作。最终,项目负责人协调整合所有成果,确保各部分顺利对接。这个例子体现了将复杂问题分而治之、逐个击破的思想,这正是分治法的核心理念。基本思想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算法的实际应用

在现代计算中,比如深度神经网络中的矩阵乘法运算,更多的是依靠GPU完成,因为矩阵乘法是一个高度并行化的问题。传统的直接三重循环方法可以被轻松映射到GPU的线程中,每个线程负责计算矩阵中的一个元素。GPU的多核架构可以同时计算数千上万个线程,从而显著缩短计算时间。总结:分治法的算法设计范式分治法是一种高效的算法设计策略,通过将原问题分解为若干个更小且形式相同的子问题,从而简化问题的求解过程。分治法广泛应用于各种计算问题,如排序、搜索、矩阵乘法等。分解将复杂问题分解为多个规模较小且与原问题性质相同的子问题解决递归地求解这些子问题,当子问题规模足够小时直接求解合并将子问题的解合并成原问题的解分解过程的设计要点分解是分治法的第一步,也是最关键的一步。分解的方法可根据任务灵活设计:按规模分解在归并排序中,分解步骤将数组按照规模分成左右两个子数组,确保子问题规模相近。按值分解在快速排序中,分解步骤按照元素的值将数组分解为两部分,左边小于基准,右边大于基准。优化子问题数量在大整数相乘中,将原问题分解为3个子问题而不是4个子问题来优化效率。解决过程的优化策略递归优化虽然递归调用求解子问题能简化任务的复杂性,但是递归调用也会有隐式的开销,可改为迭代的方式优化执行效率。小规模直接求解在子问题规模较小时,直接求解问题可以避免递归开销。比如,在快速排序中,当子问题规模较小时,可使用插入排序直接求解。合并过程的设计考虑合并步骤需要设计有效的方法,以确保最终的解是正确且高效的:简单合并在归并排序中,合并步骤将两个已排序的子数组合并成一个有序的数组,从而完成整个排序过程。额外操作在最大子数组问题中,合并时需要计算跨越中点的最大子数组,而不只是简单地取左右两部分的最大值。空间权衡合并操作可能需要额外的空间。本章讨论了不同空间复杂度的合并操作,展示了算法不断演化的动机。动态规划动态规划(DynamicProgramming)是由数学家理查德·贝尔曼于20世纪50年代提出的重要算法设计策略。它通过分解问题为子问题并利用其重复性质来求解最优解,是解决优化问题的强大工具。本章将通过详细案例分析,深入介绍动态规划的工作原理,帮助读者掌握如何利用这一技术设计高效算法。捡硬币问题:初识动态规划给定一排由n个硬币组成的序列,每个硬币的面值为正整数c₁,c₂,...,cₙ。目标是在不拾取相邻两枚硬币的前提下,尽可能多地拾取硬币,使得拾取的硬币总金额最大。例如:硬币序列为[2,7,9,3,1,5],最优解为拾取{2,9,5},总金额为16元。为什么需要动态规划?枚举法的局限枚举所有可能方案,时间复杂度为指数级Θ(2ⁿ),当n较大时计算效率极低分治法的挑战n个硬币分为左右两部分，每部分各包含n/2个硬币。对左/右半部分递归求解其最大金额。然而，在合并结果时，不能简单地将左右两部分的最大金额相加动态规划的优势通过识别最优子结构,避免重复计算,将指数级复杂度降至多项式级捡硬币问题:观察[2,7,9,3,1,5]当只有一枚硬币时，能拾取的最大价值显然为该硬币的面值，即2。考虑有两枚硬币的情况（2和7）。如果选择拾取第二枚硬币（面值为7），则第一枚硬币不能被拾取，此时总金额为7；如果不拾取第二枚硬币，则能拾取的最大金额为第一枚硬币的面值2。因此在只有前两枚硬币的情况下，拾取第二枚硬币可以得到最优解。捡硬币问题:寻找最优子结构对于第i枚硬币,我们面临两种互斥的选择:拾取第i枚硬币第i-1枚硬币不能被拾取,最大金额为第i枚硬币的面值加上前i-2枚硬币的最大金额不拾取第i枚硬币最大金额与前i-1枚硬币的最大金额一致通过比较这两种情况的最大值,我们可以得到前i枚硬币的最优解。这种递推关系为动态规划提供了基础。捡硬币问题:递推公式设最大拾取的金额为F(n),我们可以写出如下递推公式:边界条件:采用自底向上的方式逐步求解F(n):首先根据F(0)和F(1)求解出F(2),然后根据F(1)和F(2)求解出F(3),依此类推,直到计算出F(n)。捡硬币问题:算法实现算法:捡硬币问题的动态规划算法输入:一个数组coins,包含n个硬币的价值输出:可以拾取的最大硬币总金额F[0]←0F[1]←coins[1]fori←2tondoF[i]←max(F[i-1],F[i-2]+coins[i])returnF[n]算法的时间复杂度为Θ(n),空间复杂度为Θ(n)。捡硬币问题:求解示例对于硬币序列[2,7,9,3,1,5],计算过程如下:i硬币值F[i-2]+coins[i]F[i-1]F[i]0---012-02277273911711431011115112111265161216最大拾取金额为16元,拾取的硬币为{2,9,5}。动态规划的求解范式01找出最优解的性质识别最优子结构,即如何通过子问题的最优解构造原问题的最优解02递归定义最优值明确如何通过子问题的最优解递归地定义原问题的最优解,并写出递推公式03自底向上求解从最小规模的问题开始,逐步扩展到原问题的规模,避免重复计算04构造最优解通过回溯,根据递推公式中的选择情况,反向推导出最优解的路径兑零钱问题给定一个正整数数组coins,表示可用的硬币面值,以及一个目标金额n,假设每种硬币可以重复使用且数量无限,问如何用最少的硬币数凑出该金额n。例如:硬币面值为[1,2,5],兑11元最少需要3个硬币,即5+5+1。此问题的目标是找到凑出目标金额的最少硬币数,属于最优化问题,可以使用动态规划来求解。兑零钱问题:最优子结构对于兑n元硬币的情况,如果我们已经知道n-c(当前金额减去某个硬币面值c)的最少硬币数,那么兑n元的最少硬币数可以通过该结果加1得到。以n=11元为例,有三种选择:兑一枚5元硬币,剩余金额为6元兑一枚2元硬币,剩余金额为9元兑一枚1元硬币,剩余金额为10元因此,F(11)可以表示为:兑零钱问题:递推公式由此,我们可以得到F(n)的递推公式:边界条件:根据上述递推公式,可以从F(0)出发,逐步迭代计算出F(1),F(2),...,F(n)。兑零钱问题:求解示例对于coins={1,2,5},n=11的情况,求解过程如下:最优解为{1,5,5},共3枚硬币。兑零钱问题:算法实现时间复杂度Θ(kn)空间复杂度Θ(n)兑零钱问题:算法实现(2)背包问题在0-1背包问题中,给定n个物品,每个物品有一个重量wᵢ和一个价值vᵢ,同时给定一个背包的容量W。我们的目标是在以下约束条件下选择物品,使得背包内物品的总价值最大化:每个物品只能选择装入背包或者不装入背包,即0-1的选择背包内所有物品的总重量不能超过容量W这是一个经典的最优化问题,可以使用动态规划高效求解。背包问题:最优子结构分析观察

例如:物品重量w=[2,2,2],价值v=[3,7,6],容量W=4。前2个物品的最优解包含物品1和2,但全局最优解却舍弃了物品1。如果已知背包容量为w−1时的最优解，是否可以构造出背包容量为w时的最优解？物品重量w=[2,2,3]，物品价值v=[4,5,7]，背包容量W=5。当背包容量为4时，最优的选择是物品1和物品2，总价值为9。然而，当背包容量为5时，最优的选择是物品2和物品3，总价值为12。显然，背包容量为5的最优解并不能通过背包容量为4的最优解直接构造出来。背包问题:最优子结构分析关键观察如果同时考虑背包容量w和物品数量i,可以通过较小的子问题推导出整体问题的最优解。最优子结构体现在两个方面:容量减少的影响(从w转化为w-wᵢ)物品数量的递减(从i转化为i-1)背包问题:递推公式用F(n,W)表示在有前n个物品、背包容量为W时的最大价值。考虑到第n个物品,我们有两个选择:不选第n个物品此时的最大价值是前n-1个物品在容量W下的最大价值,即F(n-1,W)选第n个物品此时的最大价值是前n