0-数据结构基础知识

1.1基本概念

数据、数据元素、数据项、数据对象、数据类型、抽象数据类型

• 数据就是信息的载体，描述客观事物的数字、字符和所有能输入到计算程序识别和处理符号的集合。
• 数据元素是数据的基本单位，通常当做一个整体来考虑的。例如一个简单的排队单子：

号码

取号时间

前面排队人数

上述就是数据元素，数据元素内的就是数据项

• 数据对象是具有相同性质的数据元素的集合，数据对象是数据的一个子集。

1.2数据结构三要素

分为逻辑结构、物理结构、数据的运算

• 逻辑结构

逻辑结构可以理解为数据之间的逻辑关系，类似于函数之间的关系，一对一或者多对多之类

• 物理结构

物理结构就是存储结构，就是数据存储的方式，分为： 顺序存储：物理上是连续的 链式存储：不一定连续，采用指针连接 索引存储：有一个索引表，表中每项成为索引项，一般是关键字或者地址，能够快速查找 散列存储：哈希算法，散列存储

• 数据运算

关注的是数据之间的操作

2.算法

2.1算法

算法的基本概念

基础的认知就是，算法是解决一个问题的方式方法，例如解决二元方程组的通用公式，这个方法就是一个算法。在计算机中，算法指的是高效处理数据，解决实际问题。 公式：程序 = 数据结构 + 算法 算法是对特定问题求解的一种描述。 例如：写一个求解最年轻富豪的程序 由公式得：设计数据结构个人信息数据元素：

个人信息

年龄

身家

设计算法： step1：对根据年龄排序 step2：输出对应的数据元素项

评价算法的两个标度：时间复杂度和空间复杂度

2.2时间复杂度

1.概念

事前预估算法的时间开销（T）与问题规模（N）的关系，T就是时间。说白了就是分析代码，算一下N情况下要花多少时间。

2.方法

分析代码中的执行情况，一般重点就是在循环次数、循环条件、循环内部的操作。当N足够大的时候去分析执行时间。采用大O表示法。两个结论：

• 可以只考虑阶数高的部分
• 常数项可以忽略

3.两个运算规则：

• 多项相加，取最大的
• 多项相乘，取乘积结果

4.常用比较：

$$O(1)<O(log_2 n)<)(n)<O(nlong_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

简单结论：常对幂指阶