比喻：码农——指挥作战的将军，代码——士兵和武器，数据结构和算法——兵法。
算法 引入概念问：如果a+b+c=1000,且a² + b² =c²(a,b,c为自然数)，如何求a、b、c可能的组合？
枚举法：思路：a=0,b=0,c=0 ——>a=0,b=0,c=1 ——>……——>a=0,b=1,c=0~1000……
程序实现：
import time
t1=time.time()
for a in range(0,1001):
for b in range(0,1001):
for c in range(0,1001):
if a+b+c==1000 and a**2+b**2==c**2:
print('a:{},b:{},c:{}'.format(a,b,c))
pass
t2=time.time()
print('times:{}'.format(t2-t1))
print('finished')
结果：
a:0,b:500,c:500
a:200,b:375,c:425
a:375,b:200,c:425
a:500,b:0,c:500
times:184.36142253875732
finished
算法——计算机处理信息的本质，是独立存在的一种解决问题的办法和思想。
对于算法而言，实现的语言并不重要，重要的是思想。
算法的五大特性：
- 输入：算法具有0或者多个输入
- 输出：算法至少有1个或者多个输出
- 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，而且每一个步骤可以在可接受的时间内完成。
- 确定性：算法中的每一步都有确定的含义，不会出现二义性。
- 可行性：算法的每一步都是可行的，也就是每一步都是在有限次数内完成。
import time
t1=time.time()
for a in range(0,1001):
for b in range(0,1001):
if a**2+b**2==(1000-a-b)**2:
print('a:{},b:{},c:{}'.format(a,b,(1000-a-b)))
pass
t2=time.time()
print('times:{}'.format(t2-t1))
print('finished')
结果：
a:0,b:500,c:500
a:200,b:375,c:425
a:375,b:200,c:425
a:500,b:0,c:500
times:0.8846123218536377
finished
分析：
时间大大降低！
- 实现算法程序的执行时间可以反应算法的效率，即算法的优劣。
- 然而单纯依靠程序运行的时间来比较算法的优劣并不一定是客观准确的。
- 每台机器执行的总时间不同，但是执行基本运算数量大致相同。
每台机器执行的总时间=执行基本运算数量*基本步骤的次数 - 时间复杂度：执行基本运算步骤
上面那个（第一次尝试）程序时间复杂度T=n³*2 - 由于T=n³ *2 和T=n³ *10数量级一致，后面的系数不影响图形的走势，所以令T=n³即可。
- 函数g(n)是函数f(n)的一个渐近函数，记为f(n)=O(g(n))。（“大O表示法”）
- 时间复杂度分类：
（1）最坏时间复杂度：算法完成工作最多需要多少基本操作（主要关注点）
（2）最优时间复杂度：算法完成工作最少需要多少基本操作
（3）平均时间复杂度：算法完成工作平均需要多少基本操作 - 时间复杂度基本计算规则
（1）基本操作——即只有常数项，认为时间复杂度为O(1)
（2）顺序结构——时间复杂度按照加法计算
（3）循环结构——时间复杂度按照乘法计算
（4）分支结构——时间复杂度按照最大值计算
（5）判断一个算法的效率，往往需要关注操作数量的最高次项，其它次要项和常数项可以忽略。
常见时间复杂度之间的关系：
所耗的时间从小到大：
O(1) < O(logn) < O(n) < O(n²) < O(n³) < O(2 ^ n) < O(n!) < O(n^n)
timeit模块
class timeit.Timer(stmt=‘pass’,setup=‘pass’,timer=< timer function>)
Timer——测试小段代码执行速度的类，注意等于号后面为字符串
stmt——要测试的代码语句
setup——运行代码时需要的设置
timer——定时器函数，与平台有关
timeit.Timer.timeit(number=1000000)
number——测试代码时的测试次数，默认1000000次。返回执行代码的平均消耗时间，返回float值。
#coding=utf-8
import timeit
from timeit import Timer
def t1():
li=[]
for i in range(10000):
li.append(i)
def t2():
li=[]
for i in range(10000):
li+=[i]
def t3():
li=[i for i in range(10000)]
def t4():
li=list(range(10000))
def t5():
li = []
for i in range(10000):
li.extend([i])
timer1=Timer('t1()','from __main__ import t1')
print('append:',timer1.timeit(1000))
timer2=Timer('t2()','from __main__ import t2')
print('+:',timer2.timeit(1000))
timer3=Timer('t3()','from __main__ import t3')
print('[i for i in range(10000)]:',timer3.timeit(1000))
timer4=Timer('t4()','from __main__ import t4')
print('list(range(10000)):',timer4.timeit(1000))
timer5=Timer('t5()','from __main__ import t5')
print('extend:',timer5.timeit(1000))
#测试insert、append执行效率问题
def t6():
li=[]
for i in range(10000):
li.append(i)
def t7():
li=[]
for i in range(10000):
li.insert(0,i)
timer6=Timer('t6()','from __main__ import t6')
print('append:',timer6.timeit(1000)) #append: 0.5322161
timer7=Timer('t7()','from __main__ import t7')
print('insert:',timer7.timeit(1000)) #extend: 14.7017194
list内置操作的时间复杂度
set内置操作的时间复杂度
我们如何使用python来保存班级上的学生信息？
定义- 数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型，如：int、float、char等。
- 而python给我们提供了很多数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构，叫做python的内置数据结构，比如列表、元组、字典等。
- 而有些数据组织方式需要我们自己去定义的，叫做python的扩展数据结构，比如栈、队列等
- 算法关注解决问题的思路；而数据结构是算法需要处理的问题的载体，它静态的描述了数据元素之间的关系。
- 程序=数据结构+算法
定义：将数据类型和数据类型上的运算捆到一起，进行封装。
常用的数据运算：插入、删除、修改、查找、排序。
class Stus(object):
def adds(self):
pass
def pop(self):
pass
def sort(self):
pass
def modify(self):
pass
