导图社区 Python数据结构1引入概念
用Python数据结构的第一章的内容，引入了数据结构和算法的概念和时间复杂度的计算方法和规则。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
引入概念
算法引入
算法是计算机处理信息的本质
算法是独立存在的一种解决问题的方法和思想
算法的五大特性
输入
算法有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
append
pop()
pop(i)
O(n)
insert(i, item)
del operator
iteration
contains(in)
get slice[x:y]
O(k)
del slice
set slice
O(n+k)
reverse
concatenate
sort
O(nlogn)
multiply
O(nk)
字典类型不同操作的时间复杂度
copy
get item
delete item
数据结构引入
ADT(Abstract Data Type)
指一个数据模型以及在此数学模型上的一组操作
把数据类型和数据类型上的运算困在一起进行封装
引入目的是把数据类型的表示和数据类型上运算的 实现与这些数据类型和运算在程序中的引用隔开
最常用的数据运算
插入
删除
修改
查找
排序
