《算法设计与分析》课件 chp1 算法基础

算法基础算法在计算机科学中占据核心地位,是解决各种复杂问题的基石。它不仅决定了程序的执行效率和资源利用率,还影响着软件系统的性能和可扩展性。从数据处理、人工智能到网络安全,几乎所有计算机应用都依赖高效的算法来实现功能和优化性能。本章将介绍算法的含义以及算法分析与设计的一般性框架。第一部分算法的含义什么是算法?算法是一种解决问题的方法或步骤,就像做事情的说明书,告诉你如何逐步完成一件事。做饭的例子假设当前需要解决的问题是做一顿饭,那么菜谱就是算法。它告诉你需要哪些食材,以及按照什么顺序和步骤去烹饪,最终做出一道或多道菜。查找电话号码问题是找电话号码簿中的某个名字对应的电话号码。那么算法可以设计成从第一页开始逐个查找,直到找到为止;或者直接翻到中间,看看名字位于哪一半,再继续对半查找。算法的特点输入和输出算法通常需要明确的输入和输出。输入是指需要解决的问题所依赖的数据或信息,输出则是算法处理后的结果或答案。明确性算法的每一步必须是明确且可执行的指令。比如"加盐少许"不够明确,应该具体化为"加盐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