一，引入概念
1，引例
#求a+b+c=1000，a^2+b^2=c^2,
import math
for a in range（1001）:
for b in range(1001):
for c in range(1001):
if D==a+b+c and c*c==a*a+b*b:
print (a,b,c)
else print('no')
2，算法：
3：引例的第二次尝试
c这个数和a，b有关，知道a，b就知道c了，所以：
import time
start=time.time()
for a in range(0,1001):
for b in range(0,1001):
c==1000-a-b
if c*c==a*a+b*b:
print (a,b,c)
end=time.time()
print ('times:%d'%(end-start))
对于这段程序，不同机器执行总时间不同，但是执行的基本运算数值大体相同
4，算法效率：
这时候我们来看两个程序，那同一个机器上运行总时间应该是每一次执行的基本数量的时间乘（加）吧，这就是简单的时间复杂度
以第一段程序为例：
T（n）=1000*1000*1000*2
或者:
T（n）=1000*1000*1000*10，规模是1000，若是两千呢
所以可以定义变量N
T（n）=N^3*2
T(n)=c*g(n)
g(n)=N^3
也就是T(n)与g(n)特征相似，即g(n)为T（n）的渐变函数
记T(n)=O(g(n))
5，下面引入一个概念：
6，算法分析或者说计算的条件：
让我们来算一下第二个程序的准确时间复杂度
T（n）=n^2*(1+max(0,1))=2*n^2,即T(n)=O(n^2)
7，接下来说一些常见的时间复杂度：
7，python内置类型性能分析
注：类比一下第二个程序，stmt相当于import time，setup相当于start
相差最大便是append()与insert()，为什么会这样呢，这是由于python列表使用的数据存储方式所决定的（先存疑）
8，引入数据结构：
如存学生信息可以
[('zhangsasn',23,'henan'),('zhangsasn',23,'henan'),('zhangsasn',23,'henan')]
[{'name':'zhangsan','age':23,'hometown':"beijing"}]
{"zhangsna":{"age":14,"home":"henan"},"zhangsna":{"age":14,"home":"henan"}}
python里面列表，字典，元组，set，都是python为我们封装好的高级数据结构
推荐一本书，图解算法 https://pan.baidu.com/s/1kKBItZItmN37L2op-NqMug 密码:eq1t
网友评论