绪论

基本概念（理解即可）

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别
和处理的符号的集合。数据是计算机程序加工的原料。（For Example : 声音/图像/字符串等）

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。（For Example : 书籍信息是一个数据元素，其中的书名/价格/作者/ISBN等信息作为一个又一个的数据项）

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构三要素

不难知道，数据元素之间都不是孤立存在的，一定存在某种关系，这种数据元素之间的关系我们称之为结构。根据相关特性一般可以分为以下四种：

• 集合
• 线性结构
• 树形结构
• 图状结构或网状结构
  他们说明的是数据元素之间的逻辑关系，也叫做：逻辑结构。

那么 数据结构在计算机中的表示（也称映像），也就被称作物理结构。它包括数据元素的表示和关系的表示。一般地，我们有以下几种主要的物理结构：

• 顺序存储（以物理位置相邻表示逻辑上的相邻）
• 链式存储（形成链状）
• 索引存储（建立索引表）
• 散列存储（根据关键字算存储位置）

施加在数据上的运算包括运算的定义（逻辑）和实现（物理）被称之为数据的运算。

数据类型、抽象数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。
原子类型：其值不可再分的数据类型。(如bool & int)
结构类型：其值可以再分解为若干成分（分量）的数据类型。(如class等)
抽象数据类型（Abstract Data Type，ADT）：抽象数据组织及与之相关的操作。

ADT用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。

算法和算法分析

算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。从定义上和实际，他应具备如下五种特性：

• 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
• 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

对于一个”好“算法一定要达到以下目标：

• 正确性。算法应能够正确地解决求解问题。
• 可读性。算法应具有良好的可读性，以帮助人们理解
• 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
• 高效率（时间复杂度低）与低存储量需求（空间复杂度低）

算法效率的度量

时间复杂度

一个语句的频度是指改语句在算法中被重复执行的次数。算法中所有语句的频度之和被记为$T(n)$。他是关于该算法问题规模n的函数，时间复杂度主要分析$T(n)$的数量级。算法中基本运算（最深层的语句）的频度与$T(n)$同数量级每一次通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是时间复杂度可以定义为：

$$T(n)=O(f(n))$$

当然，最终我们写出的时间复杂度应取随n增长最快的项，将其系数置为1作为时间复杂度的度量，例如$f(n)=3n^2+2n+1$，则$T(n)=O(n^2)$。

在分析时间复杂度的时候，有以下两条规则：

• 加法规则：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(\max (f(n),g(n)))$
• 乘法规则：$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

常见的渐进时间复杂度有：

$$O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

图像表示：

相应的我们还有如下定义：

最坏时间复杂度：最坏情况下算法的时间复杂度
平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
最好时间复杂度：最好情况下算法的时间复杂度

空间复杂度

算法的空间复杂度$S(n)$定义为该算法所需的存储空间，他是一个关于算法问题规模n的函数。记为：

$$S(n)=O(f(n))$$

他的计算方法与时间复杂度类似，主要分析算法中基本存储单元的使用情况。空间复杂度的计算也有加法和乘法规则。（不在赘述在此）

一个程序在执行时除了需要存储空间来存放自身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。如果算法原地工作是指算法所需的辅助空间为常量，即$S(n)=O(1)$。

也就是说：空间复杂度为$O(1)$代表算法所需辅助空间的大小与问题规模无关。

举例：

void test(int n){int a[n];int i;
}

上面代码中，数组a的大小与n有关，因此空间复杂度为$O(n)$。

void test(int n){int i;
}

上面代码中，变量i的大小与n无关，因此空间复杂度为$O(1)$。

void test(int n){int a[n][n];
}

上面代码中，数组a的大小与n有关，因此空间复杂度为$O(n^2)$。

void test(int n){int a[n];int b[n][n];int i;
}

上面代码中，数组a的大小与n有关，数组b的大小与n有关，因此空间复杂度为$S(n)=O(n^2)+O(n)+O(1)$，根据加法原则：$S(n)=O(n^2)$