常见时间复杂度之间的关系

• 所消耗的时间从小到大
• O(1) < O(logn) < O(n) < O(nlogn) < O(n2) <O(n^2logn)< O(n3) < O(2n) < O(n!) < O(nn)

Python中List内置操作时间复杂度

• python的extend方法比+的效率要高
• 尽量不要用+来操作列表，+=倒是可以
• +=是被优化过的，所以跟extend差不多
• 

Dict内置操作时间复杂度时间复杂度

数据结构

• 数据结构定义

  • 一些数据（int float str）按照一定结构 (name,age,score)组成的关系，就是数据结构

• python的内置数据结构

  • 列表 ，元组，字典
  • 自定义扩展数据结构

• 算法与数据结构

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

• 抽象数据类型(Abstract Data Type)

  • 抽象数据类型(ADT)：把数据类型和对数据类型的运算封装在一起
  • 常用的数据运算：插入、删除、修改、查找、排序

• 线性表

  • 顺序表，就是地址是连续的，列表就是顺序表的实现

    • 顺序表的基本布局（传统）：

      • 索引之所以从零开始，就是因为没有地址偏移量，
        • 比如存放int数据，int占用四字节，所以第二个元素就是从相对上一个元素，偏移1个单位（int四个字节）
      • 顺序表的构成，
        • 开头是容量和个数
        • 
        • 顺序表有两种实现方法
          • 一体式结构
            • 地址连续，从头到尾
          • 分离式结构
            • 一个头指针存放容量，个数，还有一个指向列表的指针
        • 元素存储区替换(一体式结构)
          • 线性表扩充时候，是所有元素搬迁，全部移动到新开辟的数组中
        • 元素存储区扩充（分离式结构）
          • 推荐按照数量扩充，以空间换时间
          • 每次扩充，有两种方式，一种是按数量扩充，一种是按倍数扩充
          • 按数量特点：
            • 节省空间，但是扩充操作频繁，操作次数多
          • 按倍数特点：
            • 减少了扩充操作的执行次数，但可能会浪费空间资源

    • 元素外置顺序表（存地址）

      • 

  • 链表，节点，一个元素，一个是指向下一个节点的指针。