核心内容摘要
当半数孩子陷入近视困局，这4个低成本护眼法必须学
想象一下你是一个图书管理员要管理一个巨大的图书馆。
分数据结构 —— 如何“组织”信息数据结构就是信息的“存放方式”和“组织形式”。
糟糕的数据组织没用数据结构你把所有书随便堆在一个大仓库里。
当读者要借《哈利·波特》时你只能从第一本开始一本一本地翻找。
找一本书平均要翻一半的库存极其耗时。
这就是O(n)的线性查找。
聪明的数据组织使用数据结构使用“数组/索引”Array/Index你把所有书按书名拼音顺序整齐摆放在书架上并做了一个目录索引。
找《哈利·波特》H开头你直接跑到H区快速定位。
这就像二分查找时间复杂度从O(n)降为O(log n)时间节省巨大。
使用“哈希表”Hash Table你设计了一个神奇的函数输入书名直接输出一个书架编号和层数。
要找《哈利·波特》函数告诉你“去A区第5架第3层”你一步直达。
理想情况下是O(
的常数时间查找比按顺序找快无数倍。
空间代价你可能需要预留很多书架格子空间有些格子可能是空的。
这是用空间换时间。
使用“链表”Linked List你允许读者在还书时直接把书放在“最近归还”的架子上。
每本归还的书都记录着上一本归还书的位置。
这样插入新归还的书非常快O(
只需改一下记录。
但如果你想找到最早归还的那本书就得从头一本本往后找O(n)。
这体现了不同数据结构在不同操作上的优劣。
小结数据结构节省时间/空间的原理减少不必要的步骤通过智能组织如排序、建立映射让你无需遍历所有数据。
提供高效的操作接口链表方便插入删除数组方便随机访问栈适合“撤销”操作队列适合“排队”处理。
用对结构事半功倍。
权衡与交换哈希表用更多空间换极致时间某些压缩数据结构如前缀树用计算时间换存储空间。
分算法 —— 如何“操作和处理”信息算法是基于现有数据结构解决问题的一系列“步骤”和“策略”。
让我们用排序这个经典问题来看算法如何节省时间。
任务将10000张按学号乱序的学生卡片排好序。
笨办法低效算法冒泡排序从第一张开始比较它和下一张。
如果顺序不对就交换。
一遍又一遍地扫描整个列表直到没有交换发生。
这就像不停来回巡视整个队伍每次只纠正相邻两个人的顺序。
时间复杂度是O(n²)对于10000张卡片可能需要近1亿次量级的比较操作。
极其耗时。
聪明办法高效算法快速排序 / 归并排序快速排序策略“分而治之”。
① 选一个“基准”学号。
② 把比它小的放左边比它大的放右边。
③ 对左右两堆递归地重复这个过程。
归并排序策略① 把10000张卡分成10000个单人小组自然有序。
② 两两合并成有序的2人小组再两两合并成4人有序小组…直到合并成一个整体。
这些高级算法的时间复杂度是O(n log n)。
对于10000张卡片大约只需要13万次量级的比较操作。
对比从1亿次降到13万次这就是算法节省的时间数据量越大优势越恐怖。
另一个例子搜索最短路径如地图导航笨算法枚举从A到B所有可能的路线然后比较长度。
路线数量会随着路口数指数级爆炸算到天荒地老。
高效算法Dijkstra算法像“智慧的水波”一样扩散。
从起点开始始终优先探索当前已知可达的、离起点最近的路口并不断更新到达其他路口的最短距离。
它聪明地避开了对无效路径的深入探索用O((VE)log V)的时间复杂度V是路口E是道路解决了问题。
小结算法节省时间/空间的原理利用数学规律减少重复工作如归并排序避免重复比较动态规划存储中间结果避免重复计算。
设计智能策略剪枝无效操作如最短路径算法避免探索所有分支二分查找每次淘汰一半数据。
精确分析选择最优步骤在数据量巨大时O(n²)和O(n log n)、O(n)和O(log n)的差异是“算得出”与“算不出”的天壤之别。
核心
总结它们如何联手节省时间和空间方面如何节省简单比喻节省时间
减少不必要的计算和访问。
用接近“一步到位”的方式操作。
将大问题分解为小问题高效解决。
从“逐页翻电话本”变成“按姓氏首字母跳转”再变成“直接输入名字搜索”。
节省空间
用紧凑的方式存储信息如指针、索引。
重复利用内存避免冗余存储。
用时间换空间如压缩存储用时解压。
不复印整本字典只记录每个词的页码和行号索引。
想查时再根据索引去翻原字典。
核心思想权衡与交换。
在时间与空间、代码复杂度与运行效率之间根据具体问题数据规模、操作频次、硬件环境做出最优选择。
没有银弹只有最适合当前场景的工具和策略。
最终结论算法和数据结构是程序员的内功。
它们通过提供组织信息的艺术和高效计算的科学使得计算机能够用有限的资源CPU时间、内存空间去解决规模庞大、看似复杂的问题。
学好它们你就能在编程时做出明智的选择写出既跑得快又省内存的优质程序。
在数据爆炸的时代这种能力就是核心竞争力。