基础知识

数据

数据是指所有能输入到计算机中的描述客观事物的符号，包括文本、声音、 图像、符号等。

数据元素是数据的基本单位，也称节点或记录。

数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素，数据项是不可分割的最小单位。

数据的不可分割的单位是数据类型。

以一个一维表为例，表头特定项对应的一个值为数据项；表头整体对应的一组值为数据元素；值的类型（是数值，还是字符串？）为数据类型。

干电池类型	相对电量/重量	开路电压（V）	每节价格（CNY）
碳性电池	低/轻	1.655	0.25
碱性电池	中/重	1.629	2.50
锂铁电池	高/中	1.815	5.00

数据结构

传统上，我们把数据结构分为逻辑结构和物理结构（也称作存储结构）。

• 逻辑结构：是指对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。
  • 集合结构：若干元素同属于一个集合。
  • 线性结构：元素之间最多存在一对一的关系。
  • 树形结构：元素之间最多存在一对多的关系。
  • 图形结构：元素之间存在多对多的关系。
• 物理结构：是指数据在逻辑结构在计算机中的存储形式。
  • 顺序存储：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。如数组。
  • 链式存储：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。如链表。
  • 散列存储：又称 Hash 存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。如哈希图。
  • 索引存储：是一种分别存放数据元素和元素间关系的存储方式。所有的存储结点存放在一个区域，另设置一个索引区域存储结点之间的关系。

算法

算法是是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

• 输入：算法具有零个或多个输入。
• 输出：算法至少有一个或多个输出。
• 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且在每一个步骤在可接受的时间内完成。
• 确定性：
  • 算法的每一个步骤都具有确定的含义，不会出现二义性。
  • 算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。
  • 算法的每个步骤都应该被精确定义而无歧义。
• 可行性：算法的每一步都必须是可行的，即每一步都能够通过执行有限次数完成。

算法设计还具备一些额外的可选要求。

• 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。 正确性的四个层次：
  • 算法程序没有错误。
  • 算法程序对于合法输入能够产生满足要求的输出。
  • 算法程序对于非法输入能够产生满足规格的说明。
  • 算法程序对于故意刁难的测试输入都有满足要求的输出结果。
• 可读性：算法设计另一目的是便于阅读、理解和交流。
• 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常、崩溃或莫名其妙的结果。
• 经济性：消耗的时间短、占用的硬件资源少。

时间复杂度

函数的渐近增长：对于任意的 $f(n)=a{n}^x+b{n}^y+...+pn+q$，低次项和常数的部分往往可以忽略，我们更需要关注主项/最高项的阶数。

在进行算法分析的时候，语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随 $n$ 的变化情况并确定 $T(n)$ 的数量级。算法的时间复杂度，也就是算法的时间量度，记作 $T(n)=O(f(n))$。它表示随问题规模的增大，算法执行时间的增长率和 $F(n)$ 的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度，其中 $f(n)$ 是问题规模 $n$ 的某个函数（$n$ 一般只与循环有关）。

我们常把顺序线性执行的一整段代码视为一次运算。

一般情况下，随着输入规模 $n$ 的增大，$T(n)$ 增长最慢的算法为最优算法。

推导出函数表达式的 $O(n)$ 的步骤：

1. 将常数项替换为 1。
2. 去除所有非最高次项。
3. 将最高项的系数替换为 1。

举例：请推导出 $g(n)=3n^3+n^2+4$ 的大 $O$ 阶。

$$O(n^3)$$

如果 $T(n)=O(1)$，则称其含有常数阶；如果 $T(n)=O(n)$，则称其含有线性阶；如果 $T(n)=O(n^2)$，则称其含有平方阶；如果 $T(n)=O(\log n)$，则称其含有对数阶（底数也认为是常数，故抹去，无默认值）。 此外，还有立方阶、指数阶、$n\log n$阶......

我们一般考虑的 $O(f(n))$ 都是指最恶情况。快速排序除外。

常见的时间复杂度从短耗时到长耗时排序为：

$$O(1)<O(\log n)<O(n)<O(n\log n)<o(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

空间复杂度

现在市场上所说的“复杂度”一般指时间复杂度，这也是算法发展的潮流。因此本节不做过多停留。

在程序设计的时候，我们必须衡量时间或者空间的重要性。对于不吝啬空间的运行设备来说，我们完全可以写一套低效的算法，甚至完全靠穷举，这样节省的是程序员的时间和精力，并且也降低了运算压力，但大大增加了存储开销。对于吝啬空间的运行设备，如工控设备、单片机等，我们就可以使用结构复杂但高效的算法，因为它们不需要太高的运算速度，而是需要面临各种挑战（穷举法很容易漏情况）。具体怎么调节两者的关系，需要看使用的环境需要。

算法的空间复杂度通过计算计算所需的存储空间实现，计算公式记作 $S(n)=O(f(n))$，其中 $n$ 为问题的规模，$f(n)$ 为语句关于 $n$ 所占存储空间的函数。