第一章 算法简介

学习目标

• 为学习本书剩余章节打下坚实的基础；
• 编写二分搜索算法的代码；
• 学会使用大O​记号来分析算法的运行时间；
• 介绍一种常用的算法设计技术：递归；

介绍

定义

一个算法指的是一套完成某个任务的指令集。

虽然每个代码块都可被称作一个算法，但是本书认为的算法要比普通的代码块有趣一点。

本书中选择的算法具有如下特点：执行速度快或者能解决有意思的问题。
比如

• 第1章会介绍二分搜索算法，并展示算法如何加速代码。在一个例子里，需要执行的步数从40亿降到了32！
• GPS设备使用在第6、7、8章里介绍的图算法来计算到目的地的最短路径。
• 可以使用第9章中的动态规划算法来编写玩跳棋的AI算法。

针对每一种情形，首先，本书描述该算法，并举例说明。然后，本书用大O记号描述该算法的运行时间。最后，本书探究使用同样的算法可解决的其他类型问题。

性能分析能力

学习了本书后，将学会

• 在不同的算法之间比较：该使用合并排序还是快排？该使用数组还是列表？
• 有时候，仅仅使用了一个不同的数据结构，就能带来显著的改善；

解决问题能力

学习了本书后，将学会：

• 编写一个使用图算法的、能跟随用户的AI系统；
• 制作一个使用k紧邻算法的推荐系统；
• 如何确认一个NP问题，并提出一个近似解；
• 了解应用最广泛的若干个算法；
• 应用算法知识去学习有关AI、数据库等的更具体的算法；
• 帮助您在工作中解决更大的挑战；

二分搜索