陈越-数据结构

解决问题方法的效率，跟数据的组织方式有关。
解决问题方法的效率，跟空间的利用效率有关。（递归程序对空间占用很恐怖。）
解决问题方法的效率，跟算法的巧妙程度有管。

数据结构：

• 数据对象在计算机中的组织方式
  • 逻辑结构
  • 物理存储结构
• 数据对象必定与一系列加在其上的操作相关联
• 完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

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

算法

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

空间复杂度——占用存储单元的长度
时间复杂度——耗费时间的长度

机器运算加减法远比乘除法消耗小，所以时间复杂度一般只是考虑乘除法的。

分析一般算法的效率时，考虑下面两种复杂度：

• 最坏情况复杂度
• 平均复杂度

O 最小上界
最大下界

线性表
多项式描述

• 一维数组：第 i 项表示指数为 i 的系数，问题是存在大量无效计算
• 二维数组：每一项为一个数组，其中分别是系数和对应的指数
• 链表

线性表：由同类型数据元素构成有序序列的线性结构

• 表中元素个数为线性表的长度
• 线性表没有元素，成为空表
• 表起始位置称为表头，表结束位置成表尾