1 基本概念

1.1 什么是数据结构

1.1.1 算法效率

与解决问题的效率相关的几个因素：

• 数据结构的组织形式

例子：图书的摆放
实现方法：随便放、字母排列顺序放、按类别摆放

• 空间的使用

例子：printN
实现方法：for循环、递归

• 算法的巧妙程度

C语言计时：clock()函数，CLK_TCK为机器时钟每秒所走的打点数
例子：计算多项式值
实现方法：传统方法、秦九韶算法

1.1.2 数据结构定义

数据结构：数据对象在计算机中的组织方式，可以使用抽象数据类型（ADT）描述。

1. 逻辑结构
2. 物理存储结构

要点：

1. 数据对象必定与一系列加在其上的操作相关联
2. 完成操作的方法称为算法

抽象数据类型：

• 数据类型：
  • 数据对象集
  • 操作集
• 抽象：描述数据类型的方法不依赖于具体实现
  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言无关

1.2 什么是算法

1.2.1 算法定义

算法：

• 一个有限指令集
• 接受一些输入
• 产生输出
• 一定在有限步骤之后终止
• 每条指令必须满足：
  • 有充分的明确的目标，不可以有歧义
  • 计算机能处理的范围之内
  • 描述应不依赖于任何计算机语言以及具体的实现手段

1.2.2 算法效率指标

空间复杂度S(n)：根据算法写成的程序在执行时占用的存储单元的长度。
时间复杂度T(n)：根据算法写成的程序在执行时耗费时间的长度。

1.2.3 算法复杂度的渐进表示法

表示f(n)是T(n)的一个上界；
表示f(n)是T(n)的一个下界。

常见的复杂度：
其中对于通常会考虑能否变为。

• 对于 for 循环的复杂度，等于循环次数乘以循环体的复杂度。
• if-else 结构的复杂度取决于 if 的条件判断和两个分支部分的复杂度，总体复杂度取三者中最大的。

1.3 应用实例：最大子列和