0%

【知识总结】 第一章-绪论

数据结构基本概念

基本概念和术语

  • 数据:信息的载体,描述客观事物属性,如数字、字符、所有能输入计算机中识别处理的符号集合
  • 数据元素:数据基本单位(数据表中的一行),由数据项组成
  • 数据项:数据元素不可分割的最小单位(理解成属性)
  • 数据对象:数据元素的集合,数据的子集
  • 数据类型:值的集合和定义在此集合上的一组操作的总称
    • 原子类型:值不可再分
    • 结构类型:值可以再分
    • 抽象数据类型:抽象数据组织和操作(即结构和运算)
  • 数据结构:存在关系的数据元素的集合
    • 数据指数据元素
    • 结构指数据元素之间的关系
    • 定义数据结构需要数据对象、结构关系、操作运算

数据结构的三要素

  • 逻辑结构:独立于计算机(物理存储),从逻辑上描述数据的关系,分为线性结构和非线性结构
    • 线性结构(一对一的关系)
      • 一般线性表
      • 受限线性表:栈、队列、串
      • 线性表推广:数组
    • 非线性结构
      • 集合(属于同集合的关系)
      • 树形结构(一对多的关系):一般树、二叉树
      • 图状结构(多对多的关系):有向图、无向图
  • 存储结构:计算机中对数据和关系的表示
    • 顺序存储:逻辑相邻的元素在物理上也相邻存储
      • 优点:可随机存取、节约空间
      • 缺点:只能使用相邻的整块存储单元,容易产生碎片
    • 链式存储:逻辑相邻的元素在物理上可不相邻
      • 优点:不会出现碎片,充分利用所有存储单元
      • 缺点:引入额外指针空间开销、只能顺序存取
    • 索引存储:存储信息的同时,维护一个索引表(表的每个索引项包含关键字和地址)
      • 优点:搜索速度快
      • 缺点:索引表占用额外的存储空间,增删元素时维护索引表需要额外的开销
    • 散列存储:根据关键字直接算出存储地址,又叫哈希(Hash)存储
      • 优点:检索增删操作快
      • 缺点:如果散列函数不好,可能出现大量的冲突,从而增加时间空间开销
  • 数据元素:包括运算定义和运算实现
    • 定义:针对逻辑结构,指出运算的功能效果
    • 实现:针对存储结构,指出运算的操作步骤

算法和算法评价

算法基本概念

  • 定义:问题求解步骤的描述,指令的有限序列,指令由若干操作组成
  • 特性:
    • 有穷性:算法在有穷步结束,每一步在有穷时间完成
    • 确定性:相同输入得到相同输入
    • 可行性:算法的操作可以通过已有的基本运算执行有穷次实现
    • 输入:零个或多个
    • 输出:一个或多个
  • 目标:
    • 正确性
    • 可读性
    • 鲁棒性
    • 效率和低空间开销

算法效率的度量

  • 时间复杂度:假设$n$为问题规模,$f(n)$为频度,则时间复杂度定义为$T(n)=O(f(n))$
    • 最坏时间复杂度:最坏输入情况下的时间复杂度
    • 平均时间复杂度:给定每种输入的概率后算出的时间复杂度期望
    • 最好时间复杂度:最好输入情况下的时间复杂度
    • 期望时间复杂度:针对随机算法,最坏输入情况下的期望随机复杂度。
  • 空间复杂度:定义为算法所耗费的存储空间
    • 一般认为输入的空间取决于问题,与算法无关
    • 只考虑额外空间即可
    • 原地工作算法指额外空间开销为$O(1)$

程序时间复杂度分析技巧

  • 循环体变量参与循环条件判断:考虑该变量和循环次数的关系,用循环次数参与循环条件判断
  • 循环体变量不参与循环条件判断:数学归纳法或者直接累计