Python数据结构1引入概念

用Python数据结构的第一章的内容，引入了数据结构和算法的概念和时间复杂度的计算方法和规则。

引入概念

• 算法引入
  • 算法是计算机处理信息的本质
  • 算法是独立存在的一种解决问题的方法和思想
  • 算法的五大特性
    • 输入
      • 算法有0个或多个输入
    • 输出
      • 算法至少有一个或多个输出
    • 有穷性
      • 算法在有限的步骤之后会自动结束而不是无限循环，并且每一个步 骤可以在可接受的时间内完成
    • 确定性
      • 算法中的每一步都有确定的含义，不会出二义性
    • 可行性
      • 算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
  • 实现算法程序的执行时间可以反映出算法的效率，即算法的优劣
• 时间复杂度
  • 大O计法
    • 对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐进函数(忽略常数)，记为f(n)=O(g(n))，也就是说在向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
    • 假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))。则称O(g(n))为算法A的渐进时间复杂度，记为T(n)
  • 最优时间复杂度
    • 算法完成最少需要多少基本操作
  • 最坏时间复杂度
    • 算法完成最多需要多少基本操作
  • 平均时间复杂度
    • 算法完成平均需要多少基本工作
  • 基本计算规则
    • 基本操作：只有常数项，认为其时间复杂度为O(1)
    • 顺序结构：时间复杂度按加法进行运算
    • 循环结构：时间复杂度按乘法进行运算
    • 分支结构：时间复杂度取最大值
    • 判断一个算法的效率时，往往要关注操作数量最高次项，其他次要项和常数项可以忽略
    • 在没有特殊声明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度
  • O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
  • 注意：我们主要关注算法的最坏情况，亦最坏时间复杂度
• Python内置类型性能分析
  • timeit模块
    • 可以用来测试一小段Python代码的执行速度
    • class timeit.Time(stmt='pass', setup='pass', timer=<timer function>)
      • Timer是测量一小段代码的类
      • stmt参数是要测试的代码语句
      • setup参数是运行代码时需要的设置
      • timer参数是一个定时器函数，与平台有关
  • timeit.Timer.timeit(number=10000)
• 列表类型不同操作的时间复杂度
  • index[]
    • O(1)
  • index assignment
    • O(1)
  • append
    • O(1)
  • pop()
    • O(1)
  • pop(i)
    • O(n)
  • insert(i, item)
    • O(n)
  • del operator
    • O(n)
  • iteration
    • O(n)
  • contains(in)
    • O(n)
  • get slice[x:y]
    • O(k)
  • del slice
    • O(n)
  • set slice
    • O(n+k)
  • reverse
    • O(n)
  • concatenate
    • O(k)
  • sort
    • O(nlogn)
  • multiply
    • O(nk)
• 字典类型不同操作的时间复杂度
  • copy
    • O(n)
  • get item
    • O(1)
  • delete item
    • O(1)
  • contains(in)
    • O(1)
  • iteration
    • O(n)
• 数据结构引入
  • ADT(Abstract Data Type)
    • 指一个数据模型以及在此数学模型上的一组操作
    • 把数据类型和数据类型上的运算困在一起进行封装
    • 引入目的是把数据类型的表示和数据类型上运算的 实现与这些数据类型和运算在程序中的引用隔开
    • 最常用的数据运算
      • 插入
      • 删除
      • 修改
      • 查找
      • 排序