#数据结构 data structure

#1.基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据是计算机程序加工的原料。

数据元素是数据的基本单位。通常作为一个整体进行考虑和处理，用一个数据元素描述一个个体。一个数据元素可由若干数据项组成。

数据项是构成数据元素的不可分割的最小单位。数据项如果再细分，可以称这个数据项是组合项。例如时间可以拆分为年月日。

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

• 数据对象：人
  • 数据元素（记录）：具有相同性质，出生日
    • 数据项
    • 组合项：年月日

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构这门课着重关注的是数据元素之间的关系，和对这些数据元素的操作，而不关心具体的数据项内容。

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

• 原子类型：其值不可再分的数据类型；

  bool类型，int类型

• 结构类型：其值可以再分解为若干成分(分量)的数据类型。

  结构体

抽象数据类型(Abstract Data Type, ADT)：是抽象数据组织及与之相关的操作。

定义一个ADT，就是在定义一个完整的数据结构，确定了ADT的存储结构，才能实现这种数据结构。

抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏的特性。

#2.数据结构三要素

• 1）逻辑结构
  • 集合结构
  • 线性结构：一对一
    • 线性表
    • 栈
    • 队列
    • 串
  • 树形结构：一对多
  • 图形结构：多对多

逻辑结构是从面向实际问题出发，只采用抽象的表达方式，独立于存储结构。

• 2）数据运算（基本操作）
• 3）物理结构（存储结构）
  • 顺序存储：物理上相邻
  • 非顺序（离散）存储：物理上不相邻
    • 链式存储
    • 索引存储
    • 散列存储

若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。

数据的存储结构会影响存储空间分配的方便程度。

数据的存储结构会影响对数据运算的速度。Eg：在b和d之间插入新元素

#3.算法

程序 = 数据结构 + 算法

数据结构：要处理的信息。

算法：处理信息的步骤。

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

通常用伪代码表示。

#3.1算法必须具备的5特性

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

#3.2好算法的特性

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

#3.3函数的渐进增长

函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)。

判断一个算法效率时，函数中的常熟和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

判断一个算法好不好，我们只通过少量的数据是不能做出准确的判断的。如果我们可以对比某些算法的关键执行次数函数的渐进增长性，基本就可以分析出：某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法。

#3.4算法效率的度量

先让算法运行，事后统计时间？因为在不同的机器上运行的时间不同，所以不具有参考意义，这样不可以。

还存在什么问题？

1. 和机器性能有关，如：超级计算机 v.s.单片机
2. 和编程语言有关，越高级的语言执行效率越低
3. 和编译程序产生的机器指令质量有关
4. 有些算法是不能事后再统计的，如：导弹控制算法

所以需要 事前预估算法时间。

#❗3.4.1【考点】时间复杂度

时间复杂度：时间开销T(n)与问题规模 n 之间的关系。

注：T表示“time”。

1. 加法规则：多项相加，只保留最高阶的项，且系数变为1：

$$\begin{equation}\begin{split} T(n) &= T_1(n) + T_2(n) \\ & = O(f(n)) + O(g(n)) \\ & = O( max( f(n), g(n) )) \end{split}\end{equation}$$

2. 乘法规则：多项相乘，都保留

$$\begin{equation}\begin{split} T(n) &= T_1(n) × T_2(n) \\ & = O(f(n)) × O(g(n)) \\ \end{split}\end{equation}$$

Eg:

$$\begin{equation}\begin{split} T_3(n) &= n^3 + n^2 log_2n \\ & = O(n^3) + O(n^2 log_2n) \\ & = O(n^3) \end{split}\end{equation}$$

这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。

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

结论：

• 结论1：顺序执行的代码只会影响常数项，可以忽略。
• 结论2：只需挑循环中的一个基本操作分析它的执行次数与n的关系即可。
• 结论3：如果有多层嵌套循环，只需关注最深层循环循环了几次。

---

【考点】2种题型：

408数据结构第一章1-时间复杂度以及习题讲解_哔哩哔哩_bilibili

1. for循环
   • 一个循环
   • 多层循环
     • 不同层之间无关
     • 不同层之间有联系

$$等差求和S = \frac {n(a_1+a_n)}2 \\[1em] 等比求和S = \frac {a_1(q^n-1)}{q-1}$$

2. 递归

   • 演绎推理

   • 递归表达式

【2012年408真题】求整数n（n≥0）的阶乘的算法如下，其时间复杂的是（）。

int fact(int n){
	if(n<=1) return 1;
	return n*fact(n-1);
}

可以看出这里就是使用了递归。

分析递归的问题，除了使用演绎推理，还可以写出递归的递归表达式：（如上例子的递归表达式）

$$T(n)= \begin{cases} 1 ,& n=1\\ T(n-1)+1 ,& n>1 \end{cases}$$

其中，$T(n)=1$ 就是递归出口。

$$T_1 = T(n-1)+1 \\$$

把T1再带入下一个函数T2：

T2 里的 n=n-1

$$T_2 = T({\color{red}n-1}-1)+1+1 \\ T_3 = T(n-3)+3 \\ by\ analogy\\ T_k = T(n-k)+k$$

要使得到达递归出口，就需要 $n=1$，即$n-k=1$，则 $k=n-1$。

由此可得算法的执行次数为 $n-1$。

时间复杂为$O(n)$。

---

三种复杂度：

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

#复杂度排行

常数，对数，线性，线性对数，平方，立方，指数，阶乘，幂指时间复杂度

$$O(1) <O(log_2n)< O(n) < O(nlog_2n) < \\O(n^2) <O(n^3)<O(2^n)< O(n!) <O(n^n)$$

#3.4.2空间复杂度

空间复杂度：辅助空间开销(内存开销)S 与问题规模 n 之间的关系。

注：S表示“Space”。

无论问题规模怎么变，算法本身运行所需的内存空间都是固定的常量，算法空间复杂度为 S(n)= O(1)。

所以我们要分析的是算法所需的辅助空间的大小。

算法原地工作——算法所需内存空间为常量。

1. 变量定义会增加内存开销

e.g.：int a;一个int：4B，那么就有S(n) = O(4) = O(1)

int a[n]; 那么就有S(n) = O(4n) = O(n)

int a[n][n]; 那么就有S(n) = O(n^2^)

2. 函数递归调用带来的内存开销

空间复杂度 = 递归调用深度

例：算法的时间复杂度取决于（ ）。

​ A．问题的规模 B．待处理数据的初态

​ C．计算机的配置 D．A和B

答案：D

解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。