【信奥业余科普】07：给计算机下达的“作战菜谱”——初识算法与数据结构
第七篇信奥基础知识科普：在前六篇文章中，我们见证了单台计算机从诞生到拥有操作系统大管家和高级编程语言的进化史，也看到了互联网如何将世界连为一体。但如果有了世界上最好的厨房、最棒的食材、最快的物流，却不知道菜谱，依然做不出一顿好菜。今天，我们就来聊聊计算机世界的核心灵魂——算法与数据结构。
写在前面的话：这是一系列专为对信奥（信息学奥赛）感兴趣的中小学生及家长朋友们准备的业余科普文章。笔者并非计算机历史学专家，受自身学识所限，文中若存在不严谨或考证疏漏之处，还望各位读者海涵并指正。
推出本系列的初衷主要有三点：
- 拓宽视野：在动手敲代码之前，全面了解计算机软硬件的发展脉络。
- 激发兴趣：通过深入浅出地讲述前沿技术与历史故事，希望能点燃中小学生对计算机科学的好奇心。
- 课余读物：哪怕只是作为打发闲暇时光的休闲阅读，也能让大家在轻松的氛围中收获知识。
本系列文章往期回顾：
- 【信奥业余科普】01：人类为什么要发明计算机？——从算盘到30吨的庞然大物
- 【信奥业余科普】02：给机器注入灵魂的两位天才——图灵与冯·诺依曼
- 【信奥业余科普】03：计算机的数据表示，从 0 和 1 到大千世界
- 【信奥业余科普】04：承载“0和1”的物理躯壳——从30吨的庞然大物到指甲盖大小的微缩奇迹
- 【信奥业余科普】05：搞定了硬件，怎么教它做事？——从打孔纸带到 C++ 与操作系统
- 【信奥业余科普】06：将世界连为一体——从阿帕网到无处不在的互联网
有了强大的硬件躯干、尽心尽力的大管家操作系统、听得懂的高级语言，甚至有了连通全球的网络，计算机已经万事俱备，只欠东风。
这个“东风”就是告诉计算机具体如何解决问题的指导手册——算法与数据结构。这也是信息学奥赛（信奥）最核心、最迷人、也最烧脑的部分。
一、 什么是算法（Algorithm）？——计算机的“做菜菜谱”
在日常生活中，“算法”这个词听起来很高深，但其实它无处不在。
想象一下你想做一盘经典的西红柿炒鸡蛋。你需要详细的步骤：
- 洗两个西红柿，切成块。
- 打三个鸡蛋在碗里，用力搅匀。
- 热锅下油，把鸡蛋炒熟，盛出来备用。
- 锅里再放点油，把西红柿炒出汁水，加适量盐和一条糖。
- 倒入刚才炒好的鸡蛋，翻炒均匀，出锅装盘。
这套为了解决特定问题（做出一盘菜）而规定的、有限的、明确的执行步骤，就是算法。
对于计算机而言，算法就是程序员写下的“解题思路”。比如：如何在一大堆杂乱无章的数字中迅速找到最高分？如何计算从你家到学校不堵车的最短路线？这都需要明确的算法。在 GESP 和 CSP 等信奥考试中，著名的算法有很多：枚举、贪心、排序、二分查找、深度优先搜索等等。你的算法越聪明，计算机解决问题就越快。
二、 什么是数据结构（Data Structure）？——厨房里的“高级收纳法”
如果算法是菜谱，那食材和厨具乱放行不行？
当然不行。如果你的厨房乱七八糟，调料和蔬菜扔得满地都是，锅头压在碗底，哪怕你有米其林三星级主厨的独门菜谱，真做起菜来也会手忙脚乱，甚至把糖当成了盐。
所以我们需要合理地组织和存储数据，这在计算机科学里就叫“数据结构”。
在计算机的内存仓库中，数据不是随便乱扔的，它们可以有各种各样巧妙的“站队方式”和“收纳盒”：
- 数组（Array）：就像一排整齐的储物柜，每个柜子都有专属的数字编号，只要报出编号，找东西一抓一个准。
- 栈（Stack）：就像一个细长的薯片桶。你最后放进去的那片薯片，永远是你吃的时候最先拿出来的那片（这叫“后进先出”）。
- 队列（Queue）：就像在超市结账排队，谁先排在前面，谁就最先结账走人（这叫“先进先出”）。
- 树（Tree）：就像人类的家谱或者公司的层级组织架构图，有根有枝，往下不断开枝散叶，层级分明。
三、 黄金定律：程序 = 数据结构 + 算法
早在 1976 年，著名计算机科学家尼古拉斯·沃斯（Niklaus Wirth）就提出了一个在计算机界如雷贯耳的经典公式：程序 = 数据结构 + 算法。
这句话深刻揭示了编程的真理：聪明的数据结构，配合上高效的算法，才能写出真正顶级的程序。
举个最直观的例子：你想在《新华字典》里找“信”这个字。
- 如果这本字典里的汉字没有任何规律，全都是乱序印的（糟糕的数据结构），你别无他法，只能一页一页、一行一行地从头翻到尾（这就是笨拙的顺序查找算法，耗时极大）。
- 但现实中的字典是按首字母拼音排好序的（优秀的树形或索引数据结构），所以你可以直接翻到字母 X 的区域，然后迅速定位到具体页码（这就是大名鼎鼎的二分查找算法，眨眼间就能找到）。
四、 为什么信奥要死磕算法？——时间的魔法
有些同学可能会问：“现在的电脑 CPU 速度动辄每秒几十亿次计算跑得飞起，不管多笨的方法，我让电脑死磕暴力算出来不就行了吗？”
答案是：绝对不行。在爆炸级的庞大数据面前，笨算法会让人类等到宇宙毁灭。
在信奥比赛中，评测机通常只给你的代码 1秒钟 的执行时间。
如果你在处理 10 万个复杂数据时，用了一种笨办法（比如时间复杂度为 $O(N^2)$ 的算法），那计算机需要执行大约 100 亿次基础运算！一秒钟根本跑不完，你的屏幕上只会出现超时的警告提示——TLE (Time Limit Exceeded)。
但如果你深得编程精髓，用了一种高级算法（比如时间复杂度为 $O(N \log N)$ 的巧妙方法），同样的 10 万个数据，计算次数瞬间骤降到只有区区大约 170 万次。这对现代电脑来说连热身都不算，”唰“的一下，不到 0.01 秒就瞬间输出了满分结果 AC (Accepted)。
这种能化腐朽为神奇、把几年计算时间浓缩到几毫秒的时间魔法，正是算法的魅力所在！
下期预告
到这里，我们的“信奥业余科普”系列已经带大家走过了一台计算机从诞生、发展到灵魂成型的完整旅程。
在这个充满魅力的数字世界旅程的终点，我们要抬头畅想一下未来。计算机的下一步进化是什么？当它们不再满足于只能死板地执行已经被写死的“菜谱”，而是开始自己学习、自己跟人类对话作诗、自己战胜人类围棋世界冠军时……
下一期，我们将拥抱当下整个世界最火热的终极话题——聊聊人工智能（AI），看它是如何从科幻一步一步走入我们每一个人的现实生活的。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
