Github上复旦小姐姐原创「数据结构和算法系列」
一、算法的引入
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?可以用枚举法，简单，但是计算量大。需要用至少三个循环来完成。
import time
start = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if a**2+b**2 == c**2 and a+b+c==1000:
print('a = %d,b = %d,c = %d'%(a,b,c))
end = time.time()
print('The time is %f seconds'%(end-start))
运行结果
a = 0,b = 500,c = 500
a = 200,b = 375,c = 425
a = 375,b = 200,c = 425
a = 500,b = 0,c = 500
The time is 1317 seconds
显然，运行用了很长时间。其实，枚举法也是一种算法，该算法的执行次数为1000的三次方，效率很低。
算法的概念
算法是计算机处理信息的本质。算法是独立存在的一种解决问题的方法和思想。算法的五大特性：输入；输出；有穷性；确定性；可行性。对上面程序可以进行一定优化：
import time
start = time.time()
for a in range(1001):
for b in range(1001-a):
c = 1000 - a - b
if a**2+b**2 == c**2:
print('a = %d,b = %d,c = %d'%(a,b,c))
end = time.time()
print('The time is %f seconds'%(end-start))
运行结果
a = 0,b = 500,c = 500
a = 200,b = 375,c = 425
a = 375,b = 200,c = 425
a = 500,b = 0,c = 500
The time is 0.992053 seconds
显然比上面的运行时间要短得多得多。可以大致得到一个结论：实现算法程序的执行时间可以反应出算法的效率，计算法的优劣。算法的效率衡量：执行时间（在一定程度上）反映算法效率。但是并不是绝对的，由于：（1）测试结果非常依赖测试环境：硬件不同会对结果造成很大影响。（2）测试结果受数据规模和数据本身的影响较大：如对于排序，如数据本身是有序的，可能执行时间就会相对较短，同时数据规模较小时，测试时间不一定能真实反映算法的性能。所以每台机器执行总时间不一定一致，但是执行的基本运算的数量大体相同。
二、时间复杂度大O
第一个例子中，执行的次数为：T = 1000 * 1000 * 1000 * 21000到2000时T = 2000 * 2000 * 2000 * 21000换成N时，T = n * n * n * 2 = n ^ 3 * 2 = f(n) * 2即T(n) = f(n) * 2T(n) = O(f(n))其中，n表示数据规模的大小，T(n)表示代码执行的时间，f(n)代表每行代码的执行次数总和，O表示T(n)与f(n)成正比。此即为大O时间复杂度表示法，不是代码真正的执行时间，而是代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。
三、时间复杂度分析
方法：
1.只关心循环执行次数最多的一段代码
def cal(n):
sum = 0
i = 1
for i in range(n+1):
sum += i
return sum
函数内部，前两行是常量级的执行时间，与n的大小无关，可忽略，关注循环次数最多的那一个即for循环，for循环执行了n次，所以时间复杂度为O(n)。
2.加法原则
总复杂度等于量级最大的那段代码的复杂度。
def cal(n):
sum = 0
i = 1
for i in range(100):
sum += i
for i in range(n+1):
sum += i
for i in range(n+1):
for i in range(n + 1):
pass
第一个for循环为常数循环，复杂度为O(1)，第二个for为单层循环，为O(n)，第三个for循环为双层嵌套循环，时间复杂度为O(n^2)。如T(n) = max(O(1),O(n),O(n^2)) = O(n^2)。分析算法时，存在几种可能：※最优时间复杂度：最少需要多少基本操作li = [1,2,3,4,5]列表有序，则常数时间，O(1)。※平均时间复杂度：平均需要多少基本操作※最坏时间复杂度：最多需要多少基本操作列表无序时，时间复杂度与元素个数正相关，即O(n)。最优时间复杂度和平均时间复杂度价值不大，未提供太多有用的信息，因此主要关注算法的最坏情况，亦即最坏时间复杂度。
四、常见的时间复杂度
O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(2^n)
列表比较：
执行次数实例复杂度非正式术语10O(1)常数阶3n+2O(n)线性阶2n^2^+3n+1O(n^2^)平方阶2log~2~n+10O(log~2~n)对数阶2nlog~2~n+2n+3O(nlog~2~n)nlog~2~n阶2^n^O(2^n^)指数阶
绘图说明：
各种时间复杂度图形比较
再分析：
def cal(n):
for i in range(n):
for j in range(i):
print(i,j)
要计算1+2+3+…+(n-1)=n*(n-1)/2，所以也为O(n^2)。
五、Python内置类型性能分析
timeit模块用来测试一段代码的执行时间：三个参数：stmt, setup, timer即class timeit.Timer(stmt='',setup='',timer='')Timer:测试小段代码执行时间的类;stmt:要测试的代码语句;setup:运行代码时需要的设置;timer:定时器参数,与平台有关。
#分析列表添加的执行效率
from timeit import Timer
def test1():
l = []
for i in range(1000):
l = l + [i]
def test2():
l = []
for i in range(1000):
#末尾追加
l.Append(i)
def test3():
#列表推导式
l = [i for i in range(1000)]
def test4():
l = list(range(1000))
def test5():
l = []
for i in range(1000):
#从头添加
l.insert(0,i)
#函数要加引号
t1 = Timer('test1()','from __main__ import test1')
print('add',t1.timeit(number=1000))
t2 = Timer('test2()','from __main__ import test2')
print('append',t2.timeit(number=1000))
t3 = Timer('test3()','from __main__ import test3')
print('list derivation',t3.timeit(number=1000))
t4 = Timer('test4()','from __main__ import test4')
print('list range',t4.timeit(number=1000))
t5 = Timer('test5()','from __main__ import test5')
print('insert',t5.timeit(number=1000))
打印
add 1.223421629
append 0.06038822500000007
list derivation 0.030709197000000188
list range 0.012542454999999952
insert 0.2713445080000001
易知，第一种方式最慢，insert()方法稍快，append()更快，其他的也较快。
六、数据结构的引入
数据存储方式的不同，会导致需要不同的算法进行处理,其执行效率也会不同。如在用Python中的类型来存储一个班的学生信息时,可以考虑通过列表和字典两种方式.在通过学生姓名获取其信息时,如通过列表,则要遍历这个列表,其时间复杂度为O(n)(假设学生规模为n)而通过字典存储时,可以将学生姓名作为字典的键,学生信息作为值,进行查询时不需要遍历即可快速获取到学生信息,时间复杂度为O(1).这说明数据存储方式的不同的确会导致需要的算法不同,用算法解决问题的效率也会不同。数据是一个抽象的概念,将其分类后得到程序设计语言的基本类型，如常见的int、float、char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。定义：数据结构指数据对象中数据元素之间的关系，即数据组织的方式。Python中，数据结构分为：内置数据结构：Python已经实现，不需要我们再去定义，如列表、元组、字典等；扩展数据结构：Python并未定义，需要我们自己去定义实现这些数据的组织方式，如栈、队列等。程序 = 数据结构 + 算法总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体。抽象数据类型（ADT）：指一个数据类型以及定义在此数据模型上的一组操作，即把数据类型和数据类型上的运算捆绑在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。
