数据结构和算法
程序员文章站
2024-01-19 13:02:04
...
##Python数据结构和算法
#####前言：数据结构和算法是编程的精髓所在。
版权声明：本文为博主原创文章，欢迎转载，但必须标识出处，且在文章明显位置给出原文链接
####（一）算法分析
前言：数据结构是组织和访问数据的一种系统化方式，算法实在有限时间里一步步执行某些任务的过程。
#####（1）实验研究
1.主要分析算法的的方法是运行时间和空间利用的表示
Python中可以使用time模块的time()函数，记录算法运行前的那一刻以计算法执行完成后的那一刻，并计算他们之间的差距。
from time import time
start_time=time()
run algorithm
end_time=time()
elapse=end_time-start_time
这种方法可以很好地反映出算法的效率，但是time()函数的测量是相对于"挂钟"的，很多进程共享使用CPU，所以更加准确地方法是使用CPU时钟周期数。通常运行时间依赖于输入的大小和结构。
2.计算原子操作
为了在没有进行实验时分析一个算法的执行时间，用一个高层次的算法描述直接进行分析（可以是代码片段也可以是伪代码），我们可以定义一系列原子操作。
从形式上来说，一个原子操作相当于一条低级别指令，执行时间是常数。可以简单地计算出算法的执行时间。因此，算法执行的原子操作作数t和算法的真是运行时间成正比。
3.最坏情况输入的研究
对于相同大小的输入，算法针对某些输入的运行速度比其他更快。如果把算法的运行时间表示为所有可能的相同大小的平均值的函数，进行平均情况的分析要求定义一组概率分布，通常比较复杂。
一般我们都按照最坏情况把算法的运行时间表示为输入大小n的函数。最坏情况分析比平均情况分析要容易，只需要识别最坏情况的输入能力。
算法在最坏情况下很好地执行标准是该算法的每一个输入都能很好地执行。最坏情况的设计会使得算法更加健壮。
#####（2）比较7种函数的增长率
指数函数 > 三次函数 > 二次函数 > nlogn函数 > 线性函数 > 对数函数 > 常数
向上取整合向下取整：对算法的运行时间通常是通过一个整数表示的，所以可能涉及到取整操作.
向下取整：小于或等于x的最大整数
向上取整：大于或等于x的最小整数
#####（3）大O符号
1.令f(n)和g(n)作为正实数映射正整数的函数。如果有实型常量c>0和整型常量n0>=1,满足f(n)<=cg(n) ,当n>=n0 就说f(n)是O(g(n))。也可以说f(n)是g(n)的量级，从技术上说，大O符号代表多个函数的集合。
隐形的分割线：
下面部分一些简单举例，可能有些人觉得时间复杂度可以一眼看出来为什么还要写？博主在大学期间学习数据结构就对时间复杂度和空间复杂度的定义理解的有些模糊(可能智商不够 ：)，看教科书也没看明白，虽然能很快算出来或者看出来，但未必说得清楚。
2.命题：找出最大数算法的运行时间为O(n)
证明：在循环开始之前初始化只需要固定数量的基本操作。循环每一次重复仅需要固定的基本操作，并且循环执行n次。用两格常数c1和c2表示初始化和循环体中的基本操作，可以计算出基本操作的数量c1+c2，运行时间最多是（c1+c2）n，所以得出结论，找最大数算法的运行时间为O(n)
3.证明函数8n+5是O(n)
证明：通过大O的定义，我们需要找到一个实型常量c>0和一个整数常量n0>=1,对于任意一个整数n>=n0,满足8n+5<=cn。很容易可以找到符合的整数c，比如c=13。所以函数f(n)=8n+5是O(n)
4.在多项式中的最高阶项决定了该多项式的渐进增长速率。当n>=1是，logn<=n 。我们应该尽力用最简单最精确的属于描述函数
5.大Ω
大Ω提供另一种渐进说法：一个函数的增长率大于等于另一个函数。即存在实常数c>0和整型常数n0>=1满足 f(n)>=g(n),当n>=n0时。我们就说f(n)是Ω(g(n))，表述是f(n)是g(n)的大Ω
例题：证明3nlogn-2n是Ω(nlogn)
证明：当n>2时，3nlogn-2n=nlogn+2n(logn-1)>=nlogn 。因此，我们令c=1,n0=2时，函数3nlogn-2n是Ω(nlogn)
6.大Θ
当给定一个常数因子，两个函数增长速率相同。如果f(n)是O(g(n)),且f(n)是g(n)的大Ω时，即存在实常数c1>0,c2>0和一个整数n0>=1满足 c1g(n)<=f(n)<=c2g(n)当n>=0时，我们就说f(n)是Θ(g(n))。描述为：f(n)是g(n)的大Θ
例题：3nlogn+4n+5logn是Θ(nlogn)
证明：当n>=2时，3nlogn<3nlogn+4n+5logn<(3+4+5)nlogn
#####（4）比较分析
1.比较两个算法的运行时间更低，使用大O符号依据渐进增长率给函数排升序:1,logn,n,nlogn,n2,n3,2^n
2.缓慢渐进算法由于运行时间长而被快速渐进算法所击败，但常数因子对于快速渐进算法可能更糟糕。即使硬件的更新速度飞快，但仍然不能克服缓慢渐进算法的弊端。
3.注意事项：大O符号可能会被误用，因为它们隐藏的常数因子可能非常大，例如10^100n是O(n),与运行时间为10nlogn的算法比较，虽然线性速度可能更快，但可能更倾向于使用10nlogn的算法，因为10^100是天文数字。
#####（5）算法分析示例
1.常量时间操作
Python的list类重要特征是使用整数索引j写出data[j]来访问列表中的任意元素。列表是基于数组序列进行的，列表中的元素存储在连续的内存块中。之所以能搜索到第j个元素，不是通过迭代列表中的元素，而是通过验证索引并且把索引作为底层数组得偏移量。运行时间为O(1).
2.最大值算法
在最坏情况下，给出升序排列，最大值会被重新赋值n-1次，算法运行时间是O(n)。但如果给出的是随机序列，只有当前元素比以往所有元素都大时才会进行更新，所以预期次数H=∑1/j（j从1到n）。这就是n的调和数。根据H(n)<=clogn (n>1)该算法的运行时间是O(logn)。
3.前缀平均值（时间算法）
def prefix_average1(S)
n=len(S)
A=[0]*n #初始化列表
for j in range(n): #j从0到n-1执行了n次
total=0 #执行了n次
for i in range(j+1) #执行了j+1次
total+=S[i] #执行了1+2+3+...+n次等于n(n+1)/2
A[j]=total/(j+1) #执行了n次
return A
prefix_average1的运行时间为O(n^2)
def prefix_average2(S)
n=len(S)
A=[0]*n
for j in range(n): #执行了n次
A[j]=sum(S[0:j+1]/(j+1)) #sum函数运行时间为O(j+1)
return A
prefix_average2的运行时间为O(n^2)
def prefix_average3(S)
n=len(S)
A=[0]*n
total=0
for j in range(n): #从0到n-1执行了n次
total+=S[j]
A[j]=total/(j+1)
return A
prefix_average3的运行时间为O(n)
对比以上三种算法的运行时间得出prefix_average3运行效率最高
4.三集不相交
假设A,B,C三个序列，假定任意序列没有重复值，但是不同序列间可以重复。三集不相交问题就是确定三个序列交集为空，即不存在元素x满足x∈A，x∈B，x∈C。
def disjoint1(A，B，C):
for a range A:
for b range B:
for c range C:
if a==b==c:
return Flase
return True
disjoint1中如果每个序列的长度都是n，最坏的情况下该算法的运行时间为O(n^3)。我们可以用观测来提高渐进性。如果在循坏B中发现a和b不相等时，还去遍历C来查找三个相等的数就很浪费时间了。
def disjoint2(A，B，C):
for a range A:
for b range B: #运行时间O(n^2)
if a==b: #最多出现n个相等的情况
for c range C:
if a==c: #运行时间O(n^2)
return Flase
return True
综合得出disjoint2中在最坏情况下的运行时间是O(n^2)
5.元素的唯一性
给出一个有n个元素的的序列S，求该集合内的所有元素都不相等。