大话数据结构（一）

一、基本概念
1.基本术语：数据，数据元素，数据项，数据对象，数据结构

数据：指描述客观事物的符号，能被计算机识别并处理。
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。
数据项：一个数据元素可以由若干个数据项组成。是数据最小的不可分割单位。
数据对象：数据元素的集合，数据的子集。
结构：不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

2.逻辑结构和物理结构
逻辑结构：数据元素之间的逻辑关系

1. 集合结构（类似数学中的集合）
2. 线性结构：元素之间永远是一对一对等关系，呈线性
3. 树形结构：数据元素之间存在一对多的层次关系
4. 图形结构：数据元素之间存在多对多的关系

物理结构：数据在计算机存储器中的存储形式

1. 顺序存储结构：数据元素存在于连续的存储单元里，是完全连续的
2. 链式存储结构：数据元素存在于不连续的存储单元里，互相间通过内存单元地址知道彼此的存在

3.数据类型和抽象数据类型
数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称。（C中的结构体，JAVA中的类）
分两种：
原子类型：是不可分割的基本类型。（C中short、int、long、char、float、double。JAVA中的byte、short、int、long、char、float、double、boolean）
结构类型（复合类型或者叫引用类型）：由若干个类型组成，可以再分解。
抽象数据类型：指一个数学模型及定义在该模型上的一组操作。（抽象类很典型）

4.数据结构和算法的关系

5.算法如何比较
算法的时间复杂度、空间复杂度、性能等等

6.算法的定义和特性
定义：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
特性：输入输出、有穷性、无二义性（确定性）、可行性

7.算法的要求
正确性、可读性（工程学要求）、健壮性（容错机制）、时间效率高和存储量低

8.算法的度量方法，理解为什么表示算法复杂度的函数是渐进增长的
事后统计的方法，不确定不稳定
事先分析估算的方法：
1.算法采用的策略、方法;
2.编译产生的代码的质量;
3.问题的输入规模;
4.机器执行指令的速度
一个程序的运行时间，依赖于算法的好坏和问题的输入规模。输入规模是指输入量的多少。
渐进增长：某个算法，随着n（问题规模）的增大，它会越来越优于另一算法，或者越来越差于另一算法。不会出现逆转的情况！

9.常见的复杂度阶，并了解典型的情况（常数阶、线性阶、对数阶、平方阶）
大O记法。
推导大O阶：

1. 用常数1取代运行时间中所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1,则去除这个项相乘的常数

最后得到的结果就是大O阶。

常数阶：某个式子只计算常数次就是常数阶。O(1)。
线性阶：一个for循环就是线性阶了。O(n)。
对数阶：来自于循环的次数为x的y次方等于n，求解出一个对数值。比如循环中每次自乘2,复杂度就是O(logn)了。O(logn)。
平方阶：双重次数为n的循环嵌套。O(n²).。
另外还有O(n³)、O(2ⁿ)、O(n!)、O(nⁿ)。按前面的思路组合就可以得到。


10.分析最好和最坏的情况
最坏情况是一种保证，表示不能更坏了。一般提到的运行时间都是指的是最坏的情况。
平均情况是所有情况中最有意义的，因为它是期望的运行时间。
空间复杂度是指使用的辅助空间。辅助空间大O阶为1时，我们说算法在原地工作。