1、基础知识

一、时间复杂度

1、时间复杂度比较

保留高阶的

$$O(1)<O(\log_{2}n)<O(n)<O(n\log_{2}n)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})$$

2、加法规则和乘法规则

$$T(n)=T_{1}(n)+T_{2}(n) = O(f(n)) + O(g(n)) = O(\max(f(n),g(n)))\\ T(n)=T_{1}(n)\times T_{2}(n) = O(f(n)) \times O(g(n)) = O(f(n)\times g(n))$$

二、时间复杂度

• 忽视常数项

• 关注随循环变化的变量（如数组）

• 递归调用

三、数据结构的要素

• 逻辑结构

  • 线性结构

    • 一般线性表

    • 栈和队列

    • 串

    • 数组

  • 非线性结构

    • 集合

    • 树

    • 图

• 存储结构

  • 顺序存储

  • 链式存储

  • 索引存储

  • 散列存储

• 数据的运算