1.算法引入

• 加法规则（取最大的）
  T(n,m) = T1(n) + T2(n) = O (max (f(n),g(m))

• 乘法规则
  T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))

• 一个特例（问题规模为常量的时间复杂度）
  在大O表示法里面有一个特例，如果T1(n) = O(c）， c是一个与n无关的任意常数，T2(n) = O (f(n)) 则有T(n) = T1(n) * T2(n) = O (c*f(n)) = O(f(n))，也就是说，在大O表示法中，任何非0正常数都属于同一数量级，记为O⑴。

• 复杂度与时间效率的关系
  c < log₂n < n < nlog₂n < n² < n³ < 2^n < 3^n < n! （c是一个常量）
  其中c是一个常量，如果一个算法的复杂度为c 、log₂n 、n 、 n*log₂n，那么这个算法时间效率比较高 ，如果是 2^n,3^n,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。

内置数据类型timeit，计算程序运行时间

from timeit import Timer
def f1():
    l=[]
    for i in range(1000):
        l=l+[i]

def f2():
    l=[]
    for i in range(1000):
        l.append(i)
def f3():
    l=[i for i in range(1000)]

def f4():
    l=list(range(1000))

def f5():
    l = []
    for i in range(1000):
        l.insert(0,i)

t1=Timer("f1()","from __main__ import f1")
print(t1.timeit(number=1000))
t2=Timer("f2()","from __main__ import f2")
print(t2.timeit(number=1000))
t3=Timer("f3()","from __main__ import f3")
print(t3.timeit(number=1000))
t4=Timer("f4()","from __main__ import f4")
print(t4.timeit(number=1000))
t5=Timer("f5()","from __main__ import f5")
print(t5.timeit(number=1000))
----------------------结果↓---------------------------
1.98435366028      #最差 l=l+[i]
0.0824819497658    #l.append(i)
0.0350235466377    #l=[i for i in range(1000)]
0.00975424440503   #最优 l=list(range(1000))
0.420320303196     #l.insert(0,i)

数据结构

• 数据结构：用于存储数据的组合方式
• 程序=数据结构+算法
• 算法是为了解决实际问题而设计的，数据结构是算法的载体