数据结构与算法(python)
一个不太恰当的理解, 兵法
如果将写好运行的程序比作战场, 码农就是指挥这场战斗的指挥官, 手中的代码就是被指挥的士兵和武器.
兵法就是取得这场战斗的胜利的关键所在. 运筹帷幄之中, 决胜与千里之外.
我们的数据结构和算法, 就是程序员取胜的关键. 没有看过数据结构与算法, 有事面对问题没有任何的思路, 不知如何下手;虽然大部分时间可能解决了问题, 可是对程序运行的效率和开销没有意识, 性能底下; 面对强敌时, 有着兵法, 领军打战; 同样问题时, 算法就是我们的兵法.
尝试
如果 a+b+c=1000, 且a^2+b^2=c^2(a, b, c为自然数), 如何求出所有a, b, c可能的值
第一次尝试
通过枚举a b c的值一个一个来试, 总有一个是我们想要的.
设计程序abc在1000范围内一个一个的来遍历直接三个循环算完了就得到答案了.
程序如下:
def first():
start_time = time.time()
for a in range(1000):
for b in range(1000):
for c in range(1000):
if a+b+c == 1000 and a**2 + b**2 == c**2:
print ('a:b:c:%d, %d, %d' % (a, b, c))
end_time = time.time()
print ('程序所需时间', start_time - end_time)
print ('finished!!!')
运行结果:
66.929 我们的第一次持续了66秒
什么是算法
算法是计算机处理信息的本质, 计算机的程序本质上是一个算法来告诉计算机确切的步骤执行一个指定的任务.
算法是独立存在的一种解决问题的方法和思想
对于算法而言, 实现的语言并不重要, 重要的是思想. 算法可以用多种语言来实现, 这里我选择使用python来描述.
算法的五大特性
- 输入: 算法具有0个或多个输入
- 输出: 至少有一个或多个输出
- 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性: 算法的每一步都有确定的含义, 不会出现二义性
- 可行性: 每一步都是可行的, 每一步都能够执行有限的次数完成
第二次尝试
def second():
start_time = time.time()
for a in range(1000):
for b in range(1000):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print ('a:b:c;%d, %d, %d' % (a, b, c))
end_time = time.time()
print ('花费的时间:', start_time - end_time)
print ("finished!!!!!")
if __name__ = '__main__':
second()
运行结果:
这次的时间只有0.6秒
通过这两种方法的比较得到一个算法效率衡量的问题
算法效率衡量
执行时间反应算法效率
对于同一个问题, 以上给出的两种解决算法, 通过对时间进行了测算,发现程序执行的时间相差悬殊(一个需要69秒,一个需要0.6秒), 由此推断出: 实现算法程序的执行时间可以反应出算法的效率, 即算法的优劣
时间复杂度与"大o记法"
单纯的依靠运行的时间来比较算法的优劣并不一定是客观准确的 ,程序的运行离不开计算机环境(如果两次运行程序的计算机环境不一样, 时间就不一定了, 一个在i9-9900K跑,一个在大屁股上跑, 谁比谁快不一定.完全没有可比性). 不同的计算机环境影响程序的执行时间. 所以引入时间复杂度和"大O记法"来客观反应算法的时间效率.
我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。
时间效率, 可以使用"大O记法"来表示.
**"大O记法": ****对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似.
时间复杂度: 假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)
简单举例:
for a in range(n): # a要执行n次操作
for b in range(n):# b也要执行n次操作
# 综合起来要执行n*n次操作 也就是这两次的时间复杂度为n**2
# 可以认为2n**2和100n**2是属于同一个数量级的.都是属于n**2级
最坏时间复杂度
- 最优时间复杂度: 算法完成工作最少需要多少基本操作, 反应的是最理想的情况, 没有什么参考价值
- 最坏时间复杂度: 算法完成工作最多需要多少基本操作, 提供了一种保证,算法在经历了指定的步骤一定能完成工作.
- 平均时间复杂度: 算法完成工作平均需要多少基本操作.
时间复杂度计算规则
- 基本操作, 即只有常数项,复杂度为O(1)
- 顺序结构, 按加法计算
- 循环结构按乘法计算
- 分支结构按分支执行步骤的最大值计算
- 判断算法的效率时, 只需关注操作数的最高次项, 其他可以忽略
- 没有特殊说明的时候,算法复杂度就是 最坏时间复杂度
算法分析
第一次尝试的算法核心部分复杂度:T(n)=O(n*n*n)=O(n**3)
第二次尝试:T(n) = O(n*n*(1+1)) = O(n*n) = O(n**2)
所以第二次算法时间复杂度好, 程序时间相对块点.
常见的时间复杂度
| 执行次数函数举例 | 阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线性阶 |
| 3n2+2n+1 | O(n2) | 平方阶 |
| 5log2n+20 | O(logn) | 对数阶 |
| 2n+3nlog2n+19 | O(nlogn) | nlogn阶 |
| 6n3+2n2+3n+4 | O(n3) | 立方阶 |
| 2n | O(2n) | 指数阶 |
注意，经常将log2n（以2为底的对数）简写成logn
他们之间的关系图如下:
所以消耗时间的排序也就有了
O(1) < O(logn) < O(n) < O(nlogn) < O(n**2) < O(n**3) < O(2**n) < O(n!) < O(n**n)
python 内置类型性能分析
python内部timeit模块可以用来测试python代码的执行速度
class timeit.Time(stmt='pass', setup='pass', timer=<timer function>)
timer是测量小段代码执行速度的类
stmt参数是要测试的代码语句(statment)
setup参数是运行代码需要的设置
timer参数是一个定时器函数, 与平台有关.
timer.Timer.timeit(number=100000)
Timer类中测试语句执行速度的对象方法. number参数是测试代码是的测试次数, 默认为1000000次, 方法返回执行代码的平均耗时, 一个float类型的秒数.
对四种常见的列表创建方法的性能分析
- 列表的添加
- append方法
- 列表生成器
- list方法
代码如下:
#!/usr/bin/python3
# -*- coding=utf8 -*-
"""
# @Author : pig
# @CreatedTime:2020-03-18 14:38:37
# @Description :
"""
from timeit import Timer
def tt1():
l = []
for i in range(10000):
l = l + []
def tt2():
l = []
for i in range(10000):
l.append(i)
def tt3():
l = [i for i in range(10000)]
def tt4():
l = list(range(10000))
t1 = Timer("tt1()", "from __main__ import tt1")
print ("[]+:", t1.timeit(number=1000))
t2 = Timer('tt2()', "from __main__ import tt2")
print ("append:", t2.timeit(number=1000))
t3 = Timer("tt3()", "from __main__ import tt3")
print ("[i for i in range(10000)]:", t3.timeit(number=1000))
t4 = Timer("tt4()", "from __main__ import tt4")
print ("list(range)", t4.timeit(number=1000))
对于其他指定位置的插入, 列表的生成方法测试如下:
def tt5():
l = []
for i in range(10000):
l.extend([i])
def tt6():
l = []
for i in range(10000):
l.append(i)
def tt7():
l = []
for i in range(10000):
l.insert(0, i)
def tt8():
l = []
for i in range(10000):
l += [i]
t5 = Timer("tt5()", "from __main__ import tt5")
print ("extend:", t5.timeit(number=1000))
t6 = Timer("tt6", "from __main__ import tt6")
print ("append()", t6.timeit(number=1000))
t7 = Timer("tt7()", "from __main__ import tt7")
print ("insert", t7.timeit(number=1000))
t8 = Timer("tt8()", "from __main__ import tt8")
print ("+= :", t8.timeit(number=1000))
总体结果如下:
可以自行测试pop操作, 看看pop操作的效率如何
list内置操作的时间复杂度
dict内置操作时间复杂度
数据结构
我们如何使用python中的类型来保存一个班的学生信息? 如果想要快速通过学生姓名获取其信息呢?
实际上我们考虑这个问题就需要数据结构了. 列表和字典都可以存储一个班的信息, 但是想要在列表中获取一名同学的信息时, 就要遍历这个列表, 时间复杂度为n, 而使用字典存储是, 可以通过字典的键值查询,其时间复杂度为O(1). 为了解决问题, 需要将数据保存下来, 数据的存储方式不同就需要不同的算法进行处理.效率越高越好. 列表和字典就是python内建帮我们封装好的两种数据结构.
概念
数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。
Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。
算法与数据结构的区别
数据结构只是静态的描述了数据元素之间的关系. 高效的程序需要在数据结构的基础上设计和选择算法.
程序 = 数据结构 + 算法
算法是为了解决实际问题而设计的, 数据结构是算法需要处理的问题载体
抽象数据类型(Abstract Data Type)
抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。
常用的数据运算有五种:
- 插入
- 删除
- 修改
- 查找
- 排序
