1、基础知识

一、时间复杂度

1、时间复杂度比较

保留高阶的

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)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)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))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))

二、时间复杂度

  • 忽视常数项

  • 关注随循环变化的变量(如数组)

  • 递归调用

三、数据结构的要素

  • 逻辑结构

    • 线性结构

      • 一般线性表

      • 栈和队列

      • 数组

    • 非线性结构

      • 集合

  • 存储结构

    • 顺序存储

    • 链式存储

    • 索引存储

    • 散列存储

  • 数据的运算

Last updated