数学基础知识

计量单位

  • B，字节
  • KB，千字节，2^10 = 1024 B
  • MB，兆字节，2^20 B
  • GB，吉字节，2^30 B

阶乘(factorial)

阶乘n!，指从 1 到 n 之间所有整数的乘积，n为大于 0 的整数。如：

1
5! = 1 * 2 * 3 * 4 * 5

特别地，0! = 1。

取模(modulus)

取模，指获取整除后的余数。如：

1
5 % 3 = 2

指数幂

在数学上，我们把 n 个相同因数 a 相乘的积记做a^n。这种求几个相同因数的积的运算叫做乘方，乘方的结果叫做幂。在a^n中，a叫做底数，n叫做指数。a^n读作：a的n次方，或a的n次幂。

对数

在数学中，对数是对求幂的逆运算。如果 N = a^x(a > 0, a != 1)，那么数 x 就叫做以 a 为底 N 的对数(logarithm)，记作 x=logaN。其中，a叫做对数的底数，N叫做真数，x叫做以a为底N的对数。

  • 对数在坐标上过定点 (1, 0)，即 x = 1 时，y = 0。
  • 特别地，以 10 为底的对数称为常用对数(common logarithm)，记为 lg。
  • 以无理数 e(e=2.71828) 为底的对数称为自然对数(natural logarithm)，记为 ln。
  • 零没有对数。
  • 在实数范围内，负数无对数；在复数范围内，负数有对数。

级数

级数指将数列的项依次加起来的函数。

1
∑Un = U1 + U2 + ... + Un

算法分析

渐近分析

当我们估算一种算法的时间或者其他代价时，经常忽略其系数，只关注其增长率，这称为渐近分析法。准确的说，渐近分析是当输入规模很大，或者达到极限(微积分意义上)时，对一种算法的研究。实践证明忽略这些系数很有用，因此渐近分析也广泛应用于算法比较。

并不是任何情况都能忽略常数。当算法要解决的问题规模 n 很小时，系数就会起到举足轻重的作用。

上限

算法运行时间的上限，用来表示该算法可能有的最高增长率。算法有最佳、最差、平均情况下的上限，一般估算最差情况下的上限。

算法增长率的上限，用大 O 表示。如果某种算法的增长率上限(最差情况下)是f(n)，那么就说这种算法“在集合 O(f(n)) 中”，或直接说“在 O(f(n))”中。

下限

算法下限，表示最差、最佳、平均情况下的时间下限。用 Ω 表示，读作“大欧米伽”或“欧米伽”。

Θ

当算法上限和下限相等时，可用 Θ 表示法，读作“西塔”。

算法最佳、最差、平均情况

算法的上(下)限与给定输入规模(如n)的最差(佳)情况不同，上(下)限不是用来确定运行时间(对于给定的n值，即可确定具体的运行时间)的，而是用来确定运行时间的增长率(增长率只能在n值的一个范围内确定)。对于单个点是没有增长率概念的，增长率用于体现伴随输入规模变化的代价变化。

算法的每种输入规模(如n)都存在最佳和最差情况，所以，不要误认为当输入规模尽可能小时出现算法的最佳情况，当输入规模尽可能大时出现算法的最差情况。

理想情况下，当输入规模增大时，可以确定在最佳、最差和平均情况下的增长率。

基本数据结构

线性表

线性表是由称为元素(element)的数据项组成的一种有限且有序的序列。有序，是指线性表中的每一个元素都有自己的位置。每一个元素也都有一种数据类型。

线性表中不包含任何元素时，称为空表。当前存储的元素数目称为线性表的长度；线性表的开始结点称为表头(head)；结尾结点称为表尾(tail)。

线性表的实现有两种标准方法：顺序表(array-based list 或 sequential list)和链表(linked list)。

顺序表和链表的比较：

  • 顺序表的缺点是大小事先固定，很容易造成空间不足或浪费的情况；优点是对于表中的每个元素没有浪费空间，而链表需要在每个结点上附加一个指针。
  • 链表的优点是只有实际在链表中的对象需要空间，只要存在可用的内存空间分配，链表中的元素个数就没有限制。
  • 一般规律，当线性表元素数目变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度时，使用顺序表的空间效率会更高。
  • 链表的增加/删除操作所需的时间仅为Θ(1)。而顺序表必须将其余的元素向前或向后移动，所需的平均时间和最差时间均为Θ(n)。对于许多应用，插入和删除是最主要的操作，仅就这个原因链表往往比顺序表更好。

链表分为单链表和双链表。双链表存储了两个指针(前驱和后继)，双链表与单链表相比唯一的缺点就是使用更多的空间，双链表的每一个结点需要两个指针。

字典

计算机程序一般是用来存储和检索数据的。字典，一个简单的数据库接口，被定义成一个ADT，它提供在数据库中存储、查找和删除记录的功能。

字典用关键码(key)来描述一条数据库记录，并且该关键码是可比的(comparable)。有了这样的关键码，就能够在数据库中顺序地搜索并找出给定关键码值相匹配的记录。