内容来自于《算法》(第4版)

编写一段计算机程序一般都是实现一种已有的方法来解决某个问题。这种方法大多和使用的编程语言无关。它适用于各种计算机以及编程语言。是这种方法而非计算机程序本身描述了解决问题的步骤。在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。算法是计算机科学的基础，是这个领域研究的核心。

要定义一个算法，我们可以用自然语言的描述解决某个问题或是编写一段程序来实现这个过程。

我们关注的大多数算法都需要适当地组织数据，而为了组织数据就产生了数据结构，数据结构也是计算机科学研究的核心对象，它和算法的关系非常密切。在此书中的观点是数据结构是算法的副产品或是结果，因此要理解算法必须学习数据结构。简单的算法也会产生复杂的数据结构，相应的，复杂的算法也许只需要简单的数据结构。

对于大型问题（或者是需要解决大量小型问题的应用），我们就需要设计能够有效利用时间和空间的方法了。

学习算法的主要原因是它们能节约非常多的资源，甚至能够让我们完成一些本不可能完成的任务。在某些需要处理上百万个对象的应用程序中，设计优良的算法甚至可以将程序的运行速度提高数百万倍。

在编写庞大或复杂的程序时，理解和定义问题、控制文图的复杂度和将其分解为更容易解决的子问题需要大量的工作。很多时候，分解后的子问题所需的算法实现起来比较简单。但是在大多数情况下，某些算法的选择是非常关键的，因为大多数系统资源都会消耗在它们身上。

为一项任务选择最合适的算法是困难的，这可能会需要复杂的数学分析。计算机科学中研究这种问题的分支叫做算法分析。通过分析，我也将要学习的许多算法都有着优秀的理论性能。而另一些，我则指示根据经验知道它们是可用的。

把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型。

递归

编写递归代码时最重要的有以下三点：

• 递归总有一个最简单的情况，方法的第一条语句总是一个包含return的条件语句。
• 递归调用总是尝试去解决一个规模更小的子问题，这样递归再能收敛到最简单的情况。
• 递归调用的父问题和尝试解决的子问题之间不应该有交集。

数据抽象

数据类型指的是一组值和一组对这些值的操作的集合。

抽象数据类型(ADT)是一种能够对使用者隐藏数据表示的数据类型。

对象是能够承载数据类型的实体。所有的对象都有三大重要特性：状态、标识和行为。对象的状态即数据类型中的值。对象的标识能够将一个对象区别于另一个对象。可以认为对象的标识就是它在内存中的位置。对象的行为就是数据类型的操作。数据类型的实现的唯一职责就是维护一个对象的身份，这样用例代码在使用数据类型时只需要遵守描述对象行为的API即可，无需关心对象状态的表示方法。

对象的状态可以为用例代码提供信息，或是产生某种副作用，或是被数据类型的操作所改变。但是数据类型的值的表示细节和用例代码是无关的。引用时访问对象的一种方式。Java使用术语引用类型以示和原始数据类型的区别，不同的Java实现中引用的实现细节也各不相同，但可以认为引用就是内存地址。

每种数据类型中的值都存储于一个对象中。要创建（或实例化一个对象），我们用关键字new并紧跟类名以及()（或在括号中指定一系列的参数，如果构造函数需要的话）来触发它的构造函数。构造函数没有返回值，因为它总是返回它的数据类型的对象引用。

每当用例调用了new()，系统都会：

• 为新的对象分配内存空间
• 调用构造函数初始化对象中的值
• 返回该对象的一个引用

静态方法的主要作用是实现函数；非静态（实例）方法的主要作用是实现数据类型的操作。

使用引用类型的赋值语句将会创建该引用的一个副本。赋值语句不会创建新的对象，而只是创建另一个指向某个已经存在的对象的引用。这种情况成为别名。

一个值在初始化之后不应该再被改变，使用final。

API的作用是将使用和实现分离，以实现模块化变成。

抽象数据类型是一种向用例隐藏内部表示的数据类型。

final非常不幸地只能用来保证原始数据类型的实例变量的不可变性，而无法用于引用类型的变量。如果一个引用类型的实例变量含有修饰符final，该实例变量的值（某个对象的引用）就永远无法改变了，它将永远指向同一个对象，但对象的值本身仍然是可变的。

断言是一条需要在程序的某处确认为true的布尔表达式。如果表达式的值为false，程序将会终止并报告一条出错信息。我们使用断言来确定程序的正确性并记录我们的意图。