数据结构和算法

16. 数据结构和算法

16.1 作用

大大提升程序的性能

面试高频考点

16.2 算法

为了实现业务目的的各种方法和思路

算法是独立存在的一种解决问题的方法和思想

16.2.1 五大特性

• 输入

  • 0个或多个输入

• 输出

  • 1和或多个输出

• 有穷性

  • 算法在有限的步骤后会自动结束而不会无限循环

• 确定性

  • 每一步都有确定的含义，不会出现二义性

• 可行性

  • 每一步都是可行的

16.2.2 时间效率衡量

• 时间效率 T = 操作步骤数量 * 操作步骤执行时间

16.3 时间复杂度

• 表示一个算法随着问题规模不断变化的最主要趋势

大O记法 T(n) = O(n3) 最高次项

• 计算规则

  ① 基本操作，时间复杂度为O(1)

  ② 顺序结构，加法

  ③ 循环结构，乘法

  ④ 分支结构，取最大值

  ⑤ 关注最高次项

  ⑥ 没有特殊说明时，分析的时间复杂度都是指最坏时间复杂度

• 最优最坏

  • 算法完成工作最少需要多少基本操作 → 最优时间复杂度
  • 算法完成工作平均需要多少基本操作 → 平均时间复杂度
  • 算法完成工作最多需要多少基本操作 → 最坏时间复杂度

• 常见时间复杂度

  • 

  • 

16.4 空间复杂度

• S(n) 对一个算法在运行过程中临时占用存储空间大小的度量

16.5 数据结构

存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合

16.5.1 作用

• 相同的数据用不同的数据结构存储，运行、存储效率是不同的

16.5.2 分类

• 线性结构

  • 各个节点具有线性关系

  • 特点

    • 非空集
    • 所有结点都最多只有一个直接前趋结点和一个直接后继结点

  • 栈、队列等

• 非线性结构

  • 各个结点具有多个对应关系

  • 特点

    • 非空集
    • 一个结点可能有多个直接前趋结点和多个直接后继结点

  • 树、图等

算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体