★ FEATURED ARTICLE 第一章 · 总览与决策流程第一单元算法王国的藏宝地图——拿到一道题怎样选择算法同学们欢迎你们来到算法王国今天我们先不急着学习新的 C 语法也不急着背诵任何算法模板。我们要完成一项更重要的任务当一道从未见过的编程题出现在眼前时我们怎样判断应该使用什么算法想象一下你是一名年轻的算法探险家。国王交给你一张藏宝图上面写着勇敢的探险家请穿越迷宫、寻找宝藏你可以选择不同的道路但必须在规定时间内找到宝藏。眼前出现了许多工具枚举望远镜、贪心指南针、DFS 探索绳、DP 记忆魔法、二分搜索镜……工具这么多到底该拿哪一个如果每次都随便挑一个就像去森林探险时明明要过河却拿着一把锤子拼命敲树——工具不一定不好只是用错了地方所以本单元要学习的不是某一种具体算法而是一项贯穿整个信息学竞赛学习过程的重要本领算法选择能力根据题目的要求、数据规模和问题特点选择合适的解题方法。一、第一关先看任务不要急着写代码国王交给我们三项任务。任务 A寻找金币宝箱里有 5 枚金币编号分别是 1、2、3、4、5。找出所有价值不超过 10 的金币组合。提示金币很少可以尝试一个一个地检查。任务 B收集魔法水晶背包容量有限每颗水晶的价值和重量不同。怎样选择才能让背包里的总价值尽可能大提示这是一个需要研究最优选择的问题可以考虑贪心或动态规划等方法但要先弄清具体规则。任务 C穿越魔法迷宫迷宫里有很多岔路有些路通向死胡同。怎样找到从入口到出口的路线提示可以考虑 DFS、BFS 等搜索方法具体选择取决于题目要求。你发现了吗三个任务看起来都是“解决问题”但它们的结构完全不同。任务 A可能需要检查许多种组合。任务 B需要考虑选择方案和最优结果。任务 C需要探索不同路线。因此第一条探险规则诞生了规则一先弄清楚题目要你做什么再考虑使用什么算法。千万不要看到题目中出现“最大值”就立刻使用贪心看到“迷宫”就立刻写 DFS。关键词只能提供线索不能代替分析。二、第二关给题目做一次“体检”探险队的智者告诉我们选算法之前先给题目做一次体检体检主要检查四件事。检查一题目要求什么是求最大值、最小值、方案数量还是判断“能不能做到”例如“有多少种排列”与“最少需要多少步”通常需要不同的思考方式。检查二数据有多大只有 10 个数字和有 100 万个数字解决难度完全不同。数据规模往往决定我们能否使用简单的枚举方法。检查三题目有什么特殊结构是连续区间、树、图、排列还是一组可以反复查询的数据这些结构可能提示我们使用前缀和、树形算法、图搜索或哈希表等工具。检查四时间和空间够不够一种方法即使答案正确如果运行太慢或占用内存太多也可能无法通过评测。所以我们还要估计时间复杂度和空间复杂度。这四项检查可以记成一句顺口溜先看目标再看规模寻找结构最后算账。这里的“算账”就是估计程序需要多少计算步骤、多少内存。三、第三关认识算法王国的七大探险队当我们知道题目要求什么、数据有多大之后就可以开始寻找合适的算法工具了。今天我们先认识七支常见的探险队。注意这不是全部算法而是帮助初学者建立整体印象的第一张地图。1. 暴力枚举队一个一个试适合可能的情况不多可以逐一检查的问题。口头禅“别漏掉任何一种可能”例如找出 1 到 100 中所有同时满足两个条件的整数。2. 贪心队每一步都做出合适的选择适合能够证明局部选择可以帮助得到全局最优解的问题。口头禅“每一步怎么选才能让最终结果更好”注意每一步看起来最划算不代表最后一定最优必须证明。3. DFS 深度优先搜索队沿着一条路走下去适合探索不同路线、排列、组合和图中的可达位置等问题。口头禅“先走深一点走不通就回来”它通常借助递归或栈来实现。4. 动态规划 DP 队记住过去的成果适合存在重复子问题并且能够建立状态与状态转移关系的问题。口头禅“以前算过的结果能不能留下来”例如某些爬楼梯、网格路径和背包问题。5. 二分查找队不断缩小范围适合有序数据中的查找或者答案具有单调性、能够进行有效判断的问题。口头禅“每次排除一大半不可能的范围”但不是所有问题都能二分必须满足相应条件。6. 并查集队快速判断是不是同一个圈子适合维护元素之间的连通关系例如判断两个村庄是否属于同一个连通区域。口头禅“你们是不是已经连在一起了”7. 堆与优先队列队随时找到最优先的元素适合需要反复获取当前最大值或最小值等问题。口头禅“谁最重要我马上告诉你”例如每次从一堆任务中取出优先级最高的任务。这些队伍还有许多伙伴前缀和、差分、线段树、拓扑排序、哈希表、高精度、强连通分量、状态压缩 DP 等。随着课程推进我们会逐步认识它们。但现在先记住一个原则不是算法越高级越好而是适合题目、正确可靠、效率足够的方法才是好方法。四、第四关为什么数据规模如此重要探险队长拿出了两张任务卡。第一张检查 10 个数字中的所有数字对。第二张检查 100,000 个数字中的所有数字对。假设每次检查一对数字都算作一次基本操作。如果有 (n) 个数字我们检查所有数字对大致需要 (n^2)级别的操作。当 (n10) 时n^210^2100100 次检查很轻松当 (n100000) 时n^2 100000^2 10^10也就是大约 100 亿次检查同样的算法面对不同规模的数据结果可能完全不同。1. 认识常见时间复杂度时间复杂度探险家比喻当 n100000 时的数量级O(1)直接拿到目标约 1O(\log n)每次缩小搜索范围约 17O(n)每个元素检查一次约 100,000O(n\log n)排序一类的高效处理约 1,700,000O(n^2)检查所有元素对约 10,000,000,000O(2^n)枚举所有子集等n 稍大就会非常庞大说明表格展示的是数量级估算不是程序实际运行时间。实际速度还受硬件、实现方式、常数开销和题目细节影响O(1) 也不意味着只执行一条机器指令。请观察当数据规模变大时算法之间的效率差距可能非常惊人。例如对于有序数组二分查找每次把候选范围缩小到原来的一半。查找 100,000 个元素时最多只需要大约 17 次范围缩小就能把候选范围缩到很小。而如果使用逐个查找最坏情况下可能要检查 100,000 个元素。这就是算法的魅力同一个任务换一种思考方法所需要的计算量可能差别巨大。不过也不要因此认为 O(n^2) 一定不好O(n) 一定最好。数据规模很小时简单的暴力方法可能更容易实现也完全够用。选择算法时要综合考虑题目要求、数据规模、正确性和实现难度。五、第五关绘制属于自己的算法决策地图现在我们把刚才学到的内容整理成一张探险路线图。起点读懂题目我到底要计算、判断、统计还是寻找最优解分析数据规模与限制数据有多大时间和空间允许多少计算识别问题特征是枚举、最优选择、搜索、区间查询、图论还是查找可能方案 A暴力枚举、模拟、排序等基础方法可能方案 B搜索、DP、二分、图算法等进阶方法验证与比较方法正确吗复杂度合适吗有没有反例编写程序、测试、优化用小数据验证再检查边界和效率。这张图有一个特别重要的地方中间的“识别问题特征”并不是一个只有唯一答案的路口。一道题可能同时具有多个特征存在不止一种可行算法。我们要做的是提出候选方案再根据题目条件进行验证和比较而不是机械地走一条固定路线。例如一道迷宫题可能用 DFS 找到一条可行路线如果题目要求无权迷宫中的最少步数BFS 往往更合适。问题要求改变了算法选择也可能随之改变。这就是为什么我们需要理解算法思想而不只是记住算法名字。六、第六关记住这首《算法选择顺口溜》学算法时如果每种算法都单独记忆很容易学完前面忘记后面。所以我们给算法王国编了一首顺口溜《算法王国探险歌》小数据先枚举求最优想贪心。选路径搜一搜搜索慢剪枝走。子问题想 DP集合小状压帮。区间和前缀算区间改线段树。有序查找想二分连通关系并查集。任务有序拓扑排动态最值堆来帮。快速查询想哈希复杂难题先分析这里有三个小提醒。“求最优想贪心”只是提示你考虑贪心不代表所有最优问题都能用贪心解决。“搜索慢剪枝走”意味着可以尝试剪枝但剪枝必须有依据不能把可能产生正确答案的分支随便删掉。“有序查找想二分”也不是说有序数据只能用二分。二分是否适合还要看具体操作和问题要求。这首顺口溜是帮助我们联想算法的第一张记忆卡不是可以机械套用的万能公式。七、实战演练国王要找出最高的水晶现在我们真正来做一道小题国王有 5 颗水晶它们的能量值分别是7 3 12 5 9请你帮助国王找到能量值最大的水晶。第一步分析任务题目要求什么不是统计有多少颗水晶也不是给水晶排序而是找到其中的最大值。第二步分析数据规模只有 5 个数字。当然我们可以把它们全部排序再取最后一个数字。但是为了找出最大值有必要排序吗其实不需要第三步选择算法我们只需要从左到右检查每颗水晶记录目前见过的最大值。这就是一个简单的线性扫描方法。线性扫描不是某种复杂的高级算法但它是非常重要的基础方法。很多问题都可以通过一次遍历解决。第四步手动模拟第五步写成 C 程序#include iostream using namespace std; int main() { int a[5] {7, 3, 12, 5, 9}; int mx a[0]; // 先把第一颗水晶当作最强 for (int i 1; i 5; i) { if (a[i] mx) { mx a[i]; // 发现更强的水晶就更新记录 } } cout mx endl; return 0; }运行结果12第六步探险家复盘我们没有使用 DFS没有使用动态规划也没有使用二分查找。为什么因为这个问题只要求找出最大值遍历一遍就足够了。如果先排序通常需要 O(n log n) 的时间而一次遍历只需要 O(n) 的时间。这道例题告诉我们选择算法之前先思考有没有更简单、更直接的方法。不要为了使用高级算法而使用高级算法。八、轮到你了算法探险家训练营接下来请你亲自帮助探险家选择工具。四道算法选择题1. 有 8 个不同的数字需要找出所有满足条件的数字组合。应该优先考虑什么A. 直接使用线段树B. 根据组合规则枚举并判断每种方案C. 一定使用动态规划2. 有 100,000 个数字只要求找出最大值。哪种方法通常更合适A. 遍历一次记录最大值B. 枚举所有数字对C. 先把所有排列都试一遍3. 在没有障碍的无权迷宫中要求从起点到终点的最少步数通常优先考虑什么A. BFS 广度优先搜索B. 普通 DFS 找到的第一条路线C. 高精度加法4. 题目要求反复查询数组中某个区间的元素总和。若数组不变哪种工具值得考虑A. Manacher 算法B. 前缀和C. 并查集提交答案并查看解析九、本单元的探险笔记学习到这里请把下面五句话记进自己的算法笔记。第一先理解题目。弄清楚要求计算什么、判断什么、统计什么或优化什么。第二关注数据规模。数据大小会影响简单方法是否来得及运行。第三寻找问题特征。从问题结构中寻找可能适用的算法而不是只看某个关键词。第四验证算法是否正确。可以先用小数据模拟也要考虑边界情况和可能的反例。第五比较效率与复杂度。在能够正确解决问题的前提下选择满足时间和空间限制的合适方法。最后送给每一位算法探险家一句话面对一道新题别急着问“我应该背哪个模板”先问“这道题究竟在考验我什么”。当你能够独立提出这个问题并一步一步分析出答案时你就已经迈出了从“会写代码”走向“会设计算法”的重要一步。下一单元我们将正式进入算法王国的第一支探险队——暴力枚举当我们还不知道捷径时怎样有条理地尝试所有可能
阅读完成 · 觉得有帮助？
