北京大学《计算概论》课件：第七讲算法

LECTURE07第七讲：算法北京大学《计算概论》课程课件Contents本讲主要内容北京大学《计算概论》第七讲：算法01算法的基本概念02算法的描述与三种基本结构03几种基本算法介绍04总结与回顾CHAPTER01算法的基本概念从程序设计的本质出发，理解算法的定义、特征与核心地位计算概论·第七讲计算机与程序设计的本质计算机是被动执行指令的计算工具，程序设计的核心任务是将人类的问题求解思路转化为计算机可执行的精确步骤序列，这与数学解题过程本质相通，仅描述手段不同。被动执行的计算工具计算机本身不具备自主思考和主动行动的能力，所有计算行为都依赖于人类预先编写的指令序列。每一条指令都必须明确、精确，计算机严格按照指令顺序执行，不会自行理解意图或补充遗漏步骤。形式化的问题求解程序设计的本质是将问题求解方案转化为计算机能够理解并执行的形式化描述。这要求设计者将模糊的自然语言思维转化为精确的逻辑结构和算法步骤，确保每个环节都可被机器识别和处理。与数学解题的逻辑同构程序设计过程与中学数学解题过程在逻辑上高度一致：先确定方法步骤，再用特定语言精确表达。数学使用公式和符号，编程使用代码和语法，两者都是将思维转化为可执行、可验证的形式化系统。COMPUTATION·LECTURE07程序=数据结构+算法图灵奖得主沃斯的经典公式揭示了程序设计的两大支柱：算法提供方法路径，数据结构提供数据模型，二者结合方能构成完整程序。起源·沃斯于1976年在《算法+数据结构=程序设计》中提出该公式，奠定结构化程序设计理论基础程序·刻画现实世界、解决现实问题，程序设计语言是实现目标的工具算法·问题求解方案的形式化描述，定义从输入到输出的精确步骤序列数据结构·现实世界数据的抽象模型，决定数据在计算机中的存储和组织方式框架·程序是在特定数据结构上对抽象算法的具体表述，三者构成完整设计框架尼克劳斯·沃斯（NiklausWirth）·苏黎世联邦理工学院·1984年图灵奖得主DEFINITION算法的严格定义算法是为解决特定问题而设计的一组严格定义的动作序列，它从确定的初始状态出发，经过有限步骤后必然终止于确定状态，是程序设计中最核心的抽象概念。算法的本质为解决一个问题所采取的方法和步骤，是问题求解方案的精确形式化描述。形式化描述严格定义的动作算法是由严格定义的动作组成的过程，每一步操作都必须明确、无歧义。无歧义有限性约束给定初始状态后，经过有限步骤必然结束在确定的终止状态。必然终止程序化实现大多数算法可以用程序实现，常用算法通常被封装为算法库供程序员直接调用。算法库AlgorithmThinking算法思维实例：把大象关进冰箱通过经典趣味问题展示算法的核心思想——将问题分解为有序、明确的操作步骤序列，体现算法"分而治之"的基本思维模式。STEP00问题描述如何将一头大象关进冰箱？看似无从下手，但用算法思维可分解为明确的步骤序列，让复杂问题变得清晰可控。分解问题STEP01打开冰箱门执行一个前置操作，为后续动作创造条件。这是算法执行的必要准备阶段，确保环境就绪。前置操作STEP02把大象推进冰箱执行核心动作，完成问题的主要目标。这是算法的关键步骤，直接解决核心诉求。核心动作STEP03关上冰箱门执行收尾操作，确保最终状态的完整性。算法执行完毕后，需要确认结果并恢复环境。收尾操作ALGORITHM算法实例：从一组正整数中找最大数通过"找最大数"这一经典实例，展示算法从具体步骤到通用模式的构建过程，体现逐步精化的算法设计方法论。01问题定义给定一组正整数，设计一个通用方法找出其中的最大值。这是算法设计中最基础的问题类型，要求输出唯一且确定的结果。输入约束唯一输出02初始方案设Largest为第一个数，依次与后续各数比较，若更大则更新Largest。遍历完成后，Largest即为所求最大值。顺序扫描动态维护03逐步求解从简单假设出发，通过反复比较和条件更新，逐步逼近正确答案。每次比较都缩小候选范围，确保最终结果的准确性。迭代推进收敛保证04基本模式定义初始状态、设定比较规则、执行迭代更新。这一模式可推广至求最小值、查找特定元素等同类问题。模式抽象通用扩展算法设计方法论算法精化与泛化：从特殊到通用算法设计的核心能力在于将针对特定规模的具体步骤精化为可复用的通用模式，通过引入循环结构和变量抽象，使算法能够处理任意规模的数据。01算法精化：将"比较第二个数、第三个数……"等具体步骤统一为"比较当前数与Largest"的通用操作，消除步骤间的冗余差异。REFINE02算法泛化：引入总数N和位置指针p，使算法从处理固定5个数扩展为处理任意N个正整数，获得规模无关性。GENERALIZE03循环结构的引入：S1比较更新，S2判断p是否小于N，若小于则p加1并返回S1，形成迭代直至遍历完成。ITERATE04核心方法论："精化—泛化"过程体现从具体问题到通用方案的抽象能力，是算法设计中最重要的思维范式。ABSTRACTCOMPUTATIONFUNDAMENTALS算法的五大基本特征算法必须具备输入、输出、有穷性、确定性和可行性五个基本特征，这五条标准是判断一个计算过程是否构成严格意义上"算法"的根本依据。输入算法可以有零个或多个外部输入量，作为算法执行的初始数据。Input·≥0输出算法必须至少产生一个输出量，与输入之间存在某种确定的关系。Output·≥1有穷性算法必须在执行有限步骤之后终止，不能陷入无限循环。FiniteSteps确定性每一步操作都必须有确切含义，不存在歧义，相同输入必然产生相同输出。NoAmbiguity可行性所有操作都必须是可执行的基本运算，能在有限时间内完成。Executable计算概论·第七讲算法的重要性与学习意义算法是连接数学理论与计算实践的核心桥梁，既是程序设计的灵魂，也是衡量计算机专业人才水平的关键指标，对学生的数学思维和编程能力均有深远影响。01数学与计算机的交叉核心从欧几里得算法到现代优化算法，数学思想通过算法转化为计算能力，驱动整个计算机科学的发展。交叉核心02编程的灵魂代码的正确性、效率和可维护性从根本上取决于底层算法设计的质量，算法决定了程序的上限。设计质量03专业人才的核心竞争力无论学术研究还是工业实践，扎实的算法功底都是计算机专业人才不可替代的关键能力。核心竞争力04课程学习的重要基石本讲被定位为"难、有意思、数学与编程的基础"，是后续课程深入学习的关键起点。重要基石CHAPTER02算法的描述与三种基本结构掌握顺序、选择、循环三种控制结构，学会用流程图精确描述算法AlgorithmDescription算法的三种描述方法算法可以通过自然语言、伪代码和流程图三种方式进行描述，各有适用场景：自然语言适合初步沟通，伪代码兼顾可读性与精确性，流程图则以标准化图形实现直观严谨的过程表达。自然语言描述使用中文或英文文字表述算法步骤，通俗易懂但容易产生歧义，适合初步方案沟通与需求讨论。初步沟通伪代码描述采用类似编程语言的结构化书写方式，不拘泥于具体语法，兼顾可读性与逻辑精确性。精确性流程图描述使用标准化的图形符号——矩形、菱形、箭头等——表示算法流程，直观严谨，是本讲重点内容。本讲重点FLOWCHARTSYMBOLS流程图基本符号流程图使用标准化的图形符号来精确描述算法的执行过程，掌握起止框、处理框、判断框、输入输出框和流程线五种基本符号是绘制和阅读流程图的基础。起止框椭圆形标记算法的开始和结束位置，每个流程图有且仅有一个开始框，至少有一个结束框，用于界定算法执行的边界。Start/End处理框矩形表示一个具体的操作、计算或赋值步骤，是流程图中出现频率最高的符号，用于描述算法中的核心处理逻辑。Process判断框菱形表示条件判断，内部写入判断条件，通常有两个出口分别对应"成立"和"不成立"，是控制流程分支的关键节点。Decision输入输出框平行四边形表示数据的读取或输出操作，区分算法的外部交互与内部计算，用于描述与外部环境的参数传递和数据交换。I/O流程线箭头线表示执行的流向和顺序，连接各个符号形成完整的执行路径，箭头方向指示算法执行的先后顺序。FlowAlgorithmFundamentals顺序结构顺序结构是算法三种基本结构中最基础的形式，所有操作按从上到下的固定顺序依次执行，不存在分支和跳转，是构建复杂算法的基本组成单元。定义算法中各操作步骤按照从上到下的固定顺序依次执行，每一步执行完自动进入下一步，形成清晰的执行链条从上到下特征没有条件判断、没有循环跳转，执行路径是唯一确定的线性序列，流程清晰可预测线性序列示例交换两个变量的值——先将a赋给临时变量t，再将b赋给a，最后将t赋给b，三步依次完成a→t→b地位所有算法的基本构件，选择结构和循环结构内部都包含顺序执行的步骤，是算法设计的基石基本构件CONTROLFLOW选择结构（分支结构）选择结构根据条件判断的结果决定执行路径，是算法实现决策逻辑的核心机制，使程序能够根据不同情况采取不同行动，赋予算法处理复杂情况的能力。定义与原理根据条件表达式的真假值，选择执行不同的操作分支，实现算法中的决策逻辑。决策逻辑双分支if-else条件成立执行A路径，不成立执行B路径，两条路径互斥且必选其一。互斥必选单分支if仅当条件成立时执行特定操作，不成立则跳过该操作继续执行后续步骤。条件跳过嵌套选择在选择结构的分支内部可包含新的选择结构，形成多层决策树，处理复杂逻辑组合。多层决策树算法基础·第七讲循环结构循环结构使算法能够高效地重复执行特定操作，是处理大规模数据和迭代计算的核心机制，其正确性依赖于循环条件、循环体和终止条件的精确设计。Definition循环结构的定义当指定条件满足时，反复执行一组操作（循环体），直到条件不满足时终止。这是实现重复逻辑的基础控制结构。Elements三个关键要素循环条件（控制继续）、循环体（重复操作）、终止条件（退出判定）。三者缺一不可，共同保证循环的正确执行。Pre-check当型循环while先判断条件再决定是否执行循环体，可能一次都不执行。适用于需要先验证条件的场景。Post-check直到型循环do-while先执行一次循环体再判断条件，保证至少执行一次。适用于需要先执行操作再验证的场景。Risk核心风险终止条件设计不当会导致死循环，必须确保循环变量在每次迭代中向终止条件逼近，避免无限执行。Design设计要点明确初始状态、确保每次迭代朝终止方向推进、验证边界条件的完备性，这是编写可靠循环的关键。Algorithm·算法结构流程图实例：计算1到N的累加和通过"计算1到N累加和"这一经典实例，展示顺序结构与循环结构的组合应用，体现三种基本结构如何协同构建完整算法。STEP01⬜初始化阶段（顺序结构）设sum=0用于存储累加结果，设i=1作为循环计数变量。这是算法执行前的准备工作，为后续迭代计算奠定基础。STEP02

条件判断（选择结构）判断i≤N是否成立。若条件成立则进入循环体执行累加操作；若不成立则直接跳转至输出步骤，返回最终计算结果。STEP03▭循环体（顺序结构）执行sum=sum+i完成当前数值的累加，再执行i=i+1更新计数变量。两条语句按先后顺序依次执行，构成循环的核心计算逻辑。STEP04↻循环回路与终止循环体结束后返回条件判断节点，i持续递增直至超过N时循环终止。最终输出sum值，完成从1到N的完整累加计算。Theorem结构化程序设计定理Bohm-Jacopini定理从数学上证明了顺序、选择、循环三种基本结构的完备性——任何可计算的算法都可以仅由这三种结构组合实现，奠定了结构化程序设计的理论基础。01Bohm-Jacopini定理1966年提出：任何可计算函数都可以仅用顺序、选择、循环三种基本结构来表达196602定理意义无需发明新的控制结构，三种基本结构的组合与嵌套足以描述所有可能的算法逻辑3种完备03结构化程序设计原则程序应由三种基本结构组合而成，避免使用goto语句导致的无序跳转Nogoto04实践启示掌握三种基本结构就掌握了算法描述的完整工具集，后续重点在于结构设计和问题建模完整工具集CHAPTER03几种基本算法介绍枚举、查找、排序与递推——掌握计算机科学中最经典的基础算法思想ALGORITHMDESIGN枚举法（穷举法）枚举法通过系统地遍历所有可能的候选解并逐一验证，确保不遗漏任何正确答案，是最直观可靠的算法策略，但其效率直接受限于解空间的规模。核心思想列举问题所有可能的解，逐一检验每个候选解是否满足约束条件，保留所有符合条件的解TRAVERSE&VERIFY优点逻辑简单、实现直接、不会遗漏任何正确答案，适合解空间有限且可枚举的问题100%COVERAGE缺点时间复杂度随解空间规模指数增长，对大规模问题效率极低，需通过约束条件缩小搜索范围O(nk)COMPLEXITY经典案例百钱买百鸡——三重循环枚举公鸡、母鸡、小鸡数量，验证100钱买100鸡的约束条件百钱买百鸡ALGORITHM·查找算法顺序查找顺序查找是最基础的查找算法，通过从头到尾逐一比较实现目标定位，对数据无任何预处理要求，但平均时间复杂度为O(N)，不适合大规模数据集的高效检索。算法过程从数据集第一个元素开始，依次将每个元素与目标值比较，匹配则返回位置，遍历完毕未匹配则返回失败SEQUENTIALSCAN核心优势对数据集无任何前置要求，无需排序、无需特定数据结构，适用范围最广ZEROPREREQUISITE效率分析最好情况比较1次（目标在首位），最坏情况比较N次（目标在末位或不存在），平均约N/2次≈N/2局限性时间复杂度O(N)随数据量线性增长，面对百万级数据时性能瓶颈明显，需引入更高效的查找策略O(N)Sorting&Searching二分查找（折半查找）二分查找利用数据有序的前提，每次将查找范围缩小一半，将时间复杂度从O(N)降至O(logN)，是有序数据集上最高效的查找算法之一。01前提条件数据集必须预先排好序，这是二分查找能够正确工作的必要前提Sorted02核心过程取中间元素与目标值比较——相等则查找成功；目标较小则在左半区间递归查找；目标较大则在右半区间递归查找Divide03效率优势每次比较排除一半数据，最多需log₂N次比较即可确定目标是否存在，100万条数据最多仅需约20次比较≈20次04与顺序查找对比有序数据场景下，二分查找的O(logN)远优于顺序查找的O(N)，但牺牲了"无需排序"的通用性O(logN)ALGORITHM·排序冒泡排序冒泡排序通过反复比较相邻元素并交换逆序对来实现排序，每轮遍历将当前最大值"冒泡"至末尾，算法简单直观但时间复杂度为O(N²)，是理解排序思想的经典入门案例。核心思想反复遍历数组，比较相邻元素，若前一个大于后一个则交换，每轮遍历将当前最大值移至末尾比较交换算法过程N个元素最多N-1轮遍历，第i轮比较前N-i个相邻元素对，逐步构建有序序列N-1轮时间复杂度最好情况O(N)（已有序且设优化标志位），最坏和平均情况O(N²)，不适合大规模数据O(N²)教学价值虽然实际效率不高，但冒泡排序是理解比较-交换排序思想的经典入门案例，为学习高级排序算法奠定基础经典入门SortingAlgorithm选择排序选择排序每次从未排序部分中选取最小元素放入已排序序列末尾，通过N-1趟选择完成排序，交换次数最少（最多N-1次），但时间复杂度仍为O(N²)。01核心思想每趟从未排序的子序列中找到最小元素，将其与未排序部分的第一个元素交换，逐步扩展已排序序列。最小元素02算法过程第1趟在N个元素中找最小值与第1个元素交换，第2趟在剩余N-1个中找最小值与第2个交换，共需N-1趟。N-1趟03效率特点时间复杂度始终为O(N²)，无论数据是否有序；但交换次数最多N-1次，在交换代价高时优于冒泡排序。O(N²)04对比分析与冒泡排序时间复杂度相同，但选择排序减少了交换操作；冒泡排序通过优化可提前终止，各有适用场景。N-1次算法基础递推法递推法通过建立相邻项之间的递推关系，从已知的初始值出发逐步推导出后续所有结果，是解决序列计算和动态规划问题的核心算法思想。COREIDEA核心思想找到问题中相邻项之间的递推关系式，利用已知项逐步计算出未知项，从简单到复杂层层推进。递推关系FIBONACCI斐波那契数列F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)，已知前两项可递推出任意后续项。F(n)=F(n-1)+F(n-2)FACTORIAL阶乘计算n!=n×(n-1)!，从初始值1!=1出发，利用递推关系逐步计算出任意正整数的阶乘。n!=n×(n-1)!ESSENCE递推法的本质将复杂问题分解为"初始状态+递推规则+迭代执行"三要素，是动态规划等高级算法的基础。三要素ComplexityAnalysis基本算法效率对比不同算法在相同问题上的效率可能存在数量级差异，选对算法比优化代码更重要——二分查找的O(logN)比顺序查找的O(N)在大数据场景下优势显著。基本算法时间复杂度对比算法名称类别时间复杂度N=100万时操作次数顺序查找查找O(N)约50万次（平均）二分查找查找O(logN)最多约20次冒泡排序排序O(N²)约1万亿次选择排序排序O(N²)约1万亿次枚举法搜索视解空间而定可能指数级增长数据来源：北京大学《计算概论》·查找和排序算法的时间复杂度差异巨大，选对算法是提升效率的根本途径COMPUTATIONALCOMPLEXITY算法的时间复杂度与大O表示法大O表示法通过描述运行时间随输入规模增长的趋势来衡量算法效率，是计算机科学中评估和比较算法性能的标准工具，理解复杂度层级是算法设计的基本功。大O表示法定义描述算法运行时间或空间消耗随输入规模N增长的变化趋势，忽略常数因子和低阶项f(N)→O(g(N))常见复杂度层级从快到慢：O(1)常数级→O(logN)对数级→O(N)线性级→O(NlogN)→O(N²)平方级O(1)→O(N²)实际意义O(N²)处理100万数据需万亿次操作，O(NlogN)仅需约2000万次，差距达5万倍5万倍差距算法选择原则优先选择低复杂度算法，算法级别的效率差异是任何代码层面的优化都无法弥补的复杂度优先AlgorithmApplication算法应用：鸡兔同笼问题鸡兔同笼问题展示了同一问题可用多种算法策略求解——枚举法直观可靠但效率较低，数学推导法高效但需要建模能力，体现了算法选择中的效率与复杂度权衡。01问题描述出自《孙子算经》：笼中有鸡和兔共35只头、94只脚，求鸡和兔各有多少只。35头·94脚02枚举法求解遍历鸡的数量x从0到35，计算y=35−x，验证2x+4y是否等于94，找到x=23、y=12。枚举遍历03方程法求解建立方程组x+y=35与2x+4y=94，化简得2x+4(35−x)=94，解得x=23、y=12。方程组建模04核心启示同一问题可用不同算法策略求解，枚举法通用但低效，数学建模法高效但需抽象能力。效率权衡ALGORITHMDESIGNSTRATEGIES算法设计的基本策略算法设计有多种经典策略可供选择：分治法将大问题拆解为小问题，贪心法每步选局部最优，动态规划利用重叠子问题避免重复计算，回溯法在解空间中系统搜索。分治法将大问题分解为若干规模更小的相同子问题，递归求解后合并结果。典型应用：归并排序、快速排序、大整数乘法等。分而治之贪心策略每步选择当前最优的局部决策，期望全局最优，不回溯已做决策。典型应用：活动选择、霍夫曼编码、最小生成树。局部最优动态规划将问题分解为重叠子问题，保存已计算的子问题结果避免重复计算。典型应用：最长公共子序列、背包问题、矩阵链乘法。空间换时间COMPUTATIONALTHINKING算法与计算思维算法设计是计算思维的最高层次体现，将分解、模式