Day14：数据结构和算法基础

2020/09/21

数据结构和算法

算法就犹如战场上的兵法，面对不同问题时，应该如何去解决。找到最优解，降低功耗，提升性能。 是一种独立存在的独立解决问题思想

引入 ：枚举法

如果 a+b+c = 100 a2 +b2 = c**2 abc各个是什么
枚举法就是一个一个举例出来，看能不能成为结果。

import timestart_time = time.time()# 注意是三重循环
for a in range(0, 1001):for b in range(0, 1001):for c in range(0, 1001):if a**2 + b**2 == c**2 and a+b+c == 1000:print("a, b, c: %d, %d, %d" % (a, b, c))end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")#改进
import timestart_time = time.time()# 注意是两重循环
for a in range(0, 1001):for b in range(0, 1001-a):c = 1000 - a - bif a**2 + b**2 == c**2:print("a, b, c: %d, %d, %d" % (a, b, c))end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

算法的五大特性

1. 输入: 算法具有0个或多个输入
2. 输出: 算法至少有1个或多个输出
3. 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，且每一个步骤可以在可接受的时间内完成
4. 确定性：算法中的每一步都有确定的含义，不会出现二义性。明白每一步的意义。
5. 可行性：算法的每一步都是可行的，也就是说每一步都能够在有限的资源下执行有限的次数完成

衡量算法效率的因素

时间复杂度：就是基本运算块的数量。基本运算块就是计算机计算每一个步骤时花费的时间。基本运算块越多，计算机花费的时间就越多，算法也就越复杂。

大“o”计算法 其实对于一个算法来说，就是取和n最相关的的数量级，判断他们的渐进函数。 如果两个算法的渐进函数相等，就表示这两个函数处于同一个数量级和趋势。

算法完成工作最少需要多少基本操作，即最优时间复杂度
算法完成工作最多需要多少基本操作，即最坏时间复杂度
算法完成工作平均需要多少基本操作，即平均时间复杂度
对于最优时间复杂度，反映的只是最乐观最理想的情况，没有参考价值。

对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。所以一般情况下都是讨论最坏时间复杂度

对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证。所以也不做太多参考。

时间复杂度的几条基本计算规则

基本操作，即只有常数项，认为其时间复杂度为O(1)
顺序结构，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取 选择最多步数的那个分支
判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

# 注意是两重循环
for a in range(0, 1001):for b in range(0, 1001-a):c = 1000 - a - bif a**2 + b**2 == c**2:print("a, b, c: %d, %d, %d" % (a, b, c))

对于上面的这个代码
时间复杂度 T（n）= n * n * (1 + max(0,1)) = n ** 2 * 2 = O（n** 2）

常见时间复杂度

用内置函数测验时间复杂度

可以用timeit 模块里的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))from timeit import Timert1 = Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "seconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "seconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "seconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "seconds")

列表，字典操作复杂度顺序

其中k 代表步长 （x 和 y 之间的距离）

k添加第二个列表的元素个数

数据结构

一组数据如何被保存，这样就是数据结构。把不同的数据分类组成不同的形式就是数据结构。 比如列表就是一个数据结构，里面可以储存不同的单个数据。有相对应列表的方法，这些就让列表这种数据结构更方便使用。
程序 = 数据结构 + 算法
抽象数据类型(Abstract Data Type)的含义是即把数据类型和数据类型上的运算捆在一起，进行封装。就是说让数据可以用相应的操作方法。
比如必须要有的方法有：
插入
删除
修改
查找
排序