ADT——抽象数据类型：

• 指一个数据模型以及定义在数据模型上的一组操作。
• 通常用数据对象，数据关系，基本操作集来表示抽象数据类型。
• 抽象数据类型是一个完整的数据结构

数据结构：

• 相互之间存在一种或多种关系的数据元素的集合

• 三要素：

  • 逻辑结构
  • 存储/物理结构
  • 数据的运算




• 逻辑结构：

  • 线性结构（线性表）：栈，队列，串，广义表
  • 非线性结构：树，图，集合

算法的五大特性：

• 有穷性：有限步，每一步在有限时间内完成
• 可行性：算法中描述的操作可由已经实现的基本操作执行有限次来实现
• 确定性：每条指令有确切的定义，相同的输入只能得出相同的输出
• 输入：0 个或多个输入
• 输出：至少 1 个或多个输出

算法衡量标准：

• 时间复杂度：定性描述了算法的运行时间

  • 时间复杂度取决于两个因素：问题规模；待输入数据的性质




• 平均时间复杂度：所有可能的输入实例在等概率出现的情况下，算法期望的运行时间

  
  



• 空间复杂度：定性描述了算法所耗费的存储空间

  
  



• 算法原地工作：算法所需的辅助空间是常量