总览

第 1 章基础

算法

编写一段计算机程序一般都是实现一种已有的方法来解决某个问题。我们用算法来描述一种有限，确定，有效的并适用计算机程序来实现的解决方法的问题。

我们关注的大部分算法都需要适当地组织数据。而为了组织数据就产生了数据结构。

学习算法的主要原因是他们能节约非常多的资源，甚至能让我们完成一些本不可能完成的任务。

为一项任务选择最适合的算法是困难的，可能会需要复杂的数学分析，研究这种问题的分支叫做算法分析。

1.1 基础编程模型

先介绍了一堆的 java 基础

1.2 数据抽象

数据类型指的是一组值和一组对这些值的操作的集合。学习定义和使用数据类型，过程被称为数据抽象。

抽象数据类型(ADT)是一种能够对使用者隐藏数据表示。在使用抽象数据类型的时候，我们注意力在 API 描述的操作上，而不关心数据的展示。

1.3.3 链表

链表是一种递归的数据结构，或者为 null 或者是指向一个节点的引用，该节点含有一个泛型的元素以及一条指向另一条链表的应用。表示的是一列元素。

1.4 算法分析

使用数学分析来为算法成本建立简洁的模型并使用实验数据验证模型。

我们没法知道哪个假设是否绝对正确，我们只能验证它和我们观察的一致性。

我们想要准确测量给定程序的确切运行时间是很困难的，不过我们其实只需要近似值就可以了，我们希望的其实是把需要几秒钟，几分钟和需要几天，几个月甚至更长时间的程序区别开来。

最开始是对计算的时间进行多次采样以及画图，然后得到大体的规律，通过将普通情况下的曲线图像变成直线图像就可以得出结果了。

1.4.3 数学模型

一个程序运行的总时间和两点有关：

• 执行每条语句的耗时
• 执行每条语句的频率

前者取决于计算机，操作系统，java 编译器。后者取决于程序本身和输入。

我们在表达式里面，都是会采用近似的。因为差了幂次之后，就会很小了。

我们使用~fn来表示随着N的增大除以fn的结果趋向于1的函数。用gn~fn表示gn/fn随着N的增大趋向于1。

关键现象是执行最频繁的指令决定了程序执行的总时间。我们称这些指令为程序的内循环。

总结我们需要得到运行时间的数学模型的步骤是：

• 确定输入模型，定义问题的规模
• 识别内循环
• 根据内循环中的操作确定成本模型
• 对于给定的输入，判断这些操作的执行频率。

1.4.4 增长数量级的分类

• 常数级别：普通的语句
• 对数级别：二分查找
• 线性级别：循环
• 线性对数级别：归并排序
• 平方级别： 双层循环
• 立方级别：三层循环
• 指数级别：穷举查找

平方级别和立方级别对于大规模的问题是不可用的。很多重要问题的直观解法是平方级别的，但是我们也发现了他们的线性对数级别的算法，在实践中非常重要，因为他们能够解决的问题的规模远大于平方级别能够处理的规模。

1.4.5 设计更快的算法

学习程序的增长数量级是为了帮我们解决同一个问题设计更快的算法。比如我们想要找一堆数组中之和等于 0。看起来是 N 平方的级别。但是如果我们先归并排序，然后而二分法。就是 NlogN 以及 logN 了。也就变成了 NlogN。就可以让我们解决更大量的问题。如果是 3 个数相加的话，就变成了 N 方 logN 了。

1.4.7 注意事项

在对程序进行性能分析的时候，得到不一致或者误导性的结果的可能有很多种。大都是因为我们的猜想基于的一个或者多个假设不完全正确导致的。

• 大常数：比如我们取函数 2N2+cN 的时候，我们可能直接就忽略了后面的 cN，但是如果 c 比较大的时候，该近似就是错误的，就是说我们要对可能的大常数敏感
• 非决定性的内循环：就是说我们可能会建立错误的成本模型，问题的规模可能没有到能够忽略其他低级项的程度。就是说有些程序在内循环之外也有大量指令需要考虑。
• 指令时间：就是说每条指令执行所需的时间都是相同的假设并不总是正确的。比如，很多现在计算机使用缓存技术来管理内存，我们想要访问大数组的若干个并不相邻的值可能需要较多的时间
• 系统因素：实验的结果可能是遭到外部很大的影响的。因为首先计算机运行着很多的程序的，浏览器需要去抢资源，就算在浏览器内部也是涉及到了资源的争抢，要明白的是我们的计算机的结果是无法重现的。
• 不分伯仲：当我们比较相同任务的两个程序的时候，经常会出现有些场景更快而另一些更慢，但是这些交给专家去评估吧
• 对输入的强烈依赖：我们要能够做出与输入的相对无关才能估计算法需要的时间，比如，问题是输入中是否存在和为 0 的 3 个整数。如果输入存在就变成了一个常数级别。不存在就是立方级别。
• 多个问题参量：就是我们过去其实一直是仅需要一个参量来衡量程序的性能，参量一般是命令行参数或是输入的规模。但是多个参量也是可能的，比如需要构造一个数据结构并使用数据结构进行一系列操作的算法。数据结构的大小以及操作的次数都是问题的参量。

1.4.8 处理对于输入的依赖

许多问题下其实都是对于输入有大量的依赖的。这种情况下程序的运行时间的变化范围可能会非常大。这种情况下，我们想要预测它的性能，需要对它进行更细致的分析。

• 输入模型：更加小心的对待我们问题所要处理的输入建模，比如做出一定的假设
• 对最坏的情况下的性能的保证：有些应用程序是需要我们用一种比较悲观的角度来估计算法的性能的，因为比如一些生命相关的，刹车控制之类的等等，而且我们的程序输入可能会是恶意的用户
• 随机化算法：为性能提供保证的一种重要方法是引入随机性，比如快排的最坏情况是平方级别，但通过随机打乱，根据概率我们可以保证他的性能是线性对数的。这种保证并不是绝对的，但是他失效的可能性非常小。
• 操作序列：对于许多应用来说，算法的输入可能不只是数据，还包括用例所进行的一系列操作的顺序。比如用例压入 N 个值然后全部取出来以及 N 次压入弹出的混合操作得到的性能可能大不相同。
• 均摊分析：我们可以通过记录所有操作的总成本并除以操作总数来将成本均摊

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 981909093@qq.com