跳转至

基本概念

数据结构三要素

  • 逻辑结构
  • 物理结构(存储结构)
  • 数据的运算

数据类型和抽象数据类型

数据类型: 一个值的集合和定义在这个值的集合的一组操作的总称

  • 原子类型: 其值不可再分的数据类型

    例如: bool类型,值的范围:true, false; 可进行的操作: 与,或,非

  • 结构类型: 其值可以再分解为若干成分的数据类型

抽象数据类型: 抽象数据组织及相关的操作


时间复杂度

时间复杂度总是考虑最坏情况下的时间复杂度,以保证算法的运行时间不会比他更长

  • 加法法则: O(f(n)) + O(g(n)) = O(max(f(n), g(n))
  • 乘法法则: O(f(n)) x O(g(n)) = O(f(n) x g(n))

O(1) < O(lg n) < O(n) < O(nlg n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

算法的性能问题只有在n很大时才会暴露出来


算法原地工作: 算法所需的内存空间为常量


冀ICP备17031746号-6