数据库绪论

数据库绪论的思维导图。整理了算法、基本概念和术语、数据结构三要素的内容，欢迎查看。

第一章 绪论

• 算法
  • 程序=数据结构+算法
  • 算法的特性
    • 有穷性
      • 有穷的步骤，有穷的时间
      • 注：算法必须是有穷的，而程序可以是无穷的
    • 确定性
      • 每条指令都无歧义，相同的输入得到相同的输出
    • 可行性
    • 输入
      • 零个或多个
    • 输出
      • 一个或多个
  • 好算法的特性
    • 正确性
      • 能够正确地解决
    • 可读性
    • 健壮性
      • 输入非法数据时也能适当的进行处理，而不是产生莫名其妙的东西
    • 高效率（时间复杂度）、低存储量需求
  • 算法的时间复杂度T(n)
    • 计算技巧
      • 加法规则：多项相加，只保留最高阶的项，且系数变为1
      • 乘法规则：多项相乘，都保留
      • 0(1)<o(log2n)<o(nlog2n)<o(n^2)<o(n^3)<o(2^n)<o(n!)<o(n^n)
    • 如何计算
      • 顺序执行的代码只会影响常数项，可以忽略
      • 只需挑循环中的一个基本操作分析它的执行次数与n的关系
      • 如果有多层嵌套循环，只需关注最深层循环，循环几次
    • 三种复杂度
      • 最坏
      • 平均
      • 最好
  • 算法的空间复杂度s(n)
    • 如何计算
      • 程序代码大小固定，与问题规模无关
      • 只需关注存储空间大小与问题规模相关的变量
      • 对于递归程序，需要找到递归调用的深度x与问题规模n的关系
    • 算法原地工作——s(n)=o(1)
• 基本概念和术语
  • 数据
  • 数据项
  • 数据元素
  • 数据对象
  • 数据结构
  • 数据类型
    • 原子类型
    • 结构类型
  • 抽象数据类型ADP
• 数据结构三要素
  • 逻辑结构
    • 一对一：线性
    • 一对多：树形
    • 多对多：图
  • 数据的运算
  • 存储结构
    • 顺序
    • 链式
    • 索引
    • 散列