无锡建设公司网站,wordpress设置vip,网站建设公开,邯郸网站设计价位在学习算法的时间复杂度之前#xff0c;需要了解下面5条概念 什么是算法的时间复杂度#xff1f; 针对指定基本运算#xff0c;计数算法所做的运算次数。什么是基本运算#xff1f;比较、加法、乘法、置指针、交换…什么是输入规模#xff1f;输入串的编码长度#xff0c… 在学习算法的时间复杂度之前需要了解下面5条概念 什么是算法的时间复杂度 针对指定基本运算计数算法所做的运算次数。什么是基本运算比较、加法、乘法、置指针、交换…什么是输入规模输入串的编码长度通常是数组元素的多少、调度问题的任务个数、图的顶点数与边数等。算法的基本运算次数可以表示为输入规模的函数。给定问题和基本运算就决定了一个算法类 文章目录1 算法的两种时间复杂度1.1 例子检索问题(1)顺序检索算法(2)改进顺序检索算法2 总结1 算法的两种时间复杂度
对于相同输入规模的不同实例算法的基本运算次数也不一样所以定义了两种时间复杂度。
最坏情况下的时间复杂度W(n):算法求解输入规模为n的实例所需要最长的时间平均情况下的时间复杂度A(n): 在给定同样规模为n的实例的概率分布下算法求解这些实例所需要的平均时间。
平均情况下的时间复杂度求解公式为
A(n)∑I∈SPItIA(n) \sum_{I{\in}S} P_It_IA(n)I∈S∑PItI
其中S为规模为n的实例集实例I∈SI\in SI∈S的概率为PI .算法对实例I执行的基本运算次数为tI 在某些情况下可以假定每个输入实例的概率相等。 1.1 例子检索问题
输入非降序排列的数组L元素个数n需要检索的数x。输出j。如果x在数组L中j是x首次出现的下标。否则j0.基本运算x与L中的元素比较。
(1)顺序检索算法
j1, 将x与L[j]比较. 如果 xL[j]则算法停止输出 j如果不等则把 j 加1继续x与L[j]的比较如果 jn则停机并输出0。
实例1 2 3 4 5 x4需要比较4次 x2.5 需要比较5次
最坏情况时间复杂度
不同的输入有:2n1个分别对应
最坏情况下时间W(n)n最坏的输入x不在L中或者xL[n]还没有接触到数据结构中的数组下表不是从0开始的是从1开始的。此时要做n次比较。
平均情况的时间估计
输入实例的概率分布假设x在L中的概率是P且每个位置的概率相等。则由上文的公式得
A(n)∑i1nipn(1−p)np(n1)2(1−p)nA(n) \sum_{i1}^n i\frac{p}{n} (1-p)n \frac{p(n1)}{2}(1-p)nA(n)i1∑ninp(1−p)n2p(n1)(1−p)n
当p1/2时A(n)n14n2≈3n4A(n)\frac{n1}{4}\frac{n}{2} \approx \frac{3n}{4}A(n)4n12n≈43n 注意上述求解公式中注意理解(1-p)n 代表如果元素不存在数组中比较的次数是从头到尾。即n次不存在的概率是1-p。 (2)改进顺序检索算法
j1, 将 x与L[j]比较. 如果 xL[j]则算法停止输出 j如果 x L[j]则把 j 加1继续 x与 L[j]的比较如果 x L[j]则停机并输出0. 如果 j n则停机并输出 0。 之所以可以优化成这样是因为该算法的输入是非降序排列的数组 实例1 2 3 4 5 x 4需要比较 4 次 x 2.5需要比较 3 次
最坏情况时间复杂度W(n) n平均情况时间复杂度
输入实例的概率分布假设x在数组L中的每个位置与空隙的概率都相等。设在数组中的概率是p不在数组L中的概率是1-p。则pn1−pn1\frac{p}{n}\frac{1-p}{n1}npn11−p
则由公式计算平均时间复杂度为
A(n)∑i1nipn1−pn1n∑i1nipnpnnA(n) \sum_{i1}^n i\frac{p}{n} \frac{1-p}{n1}n \sum_{i1}^n i\frac{p}{n} \frac{p}{n}n A(n)i1∑ninpn11−pni1∑ninpnpn p(1n)2p\frac{p(1n)}{2}p2p(1n)p
当p1/2时
A(n)n434≈n4A(n)\frac{n}{4}\frac{3}{4} \approx \frac{n}{4}A(n)4n43≈4n
很明显改进后的检索算法时间复杂度减小了很多。算法的性能有所提升。
2 总结
本文的学习并不是来学习检索这个算法也不是来提升它的性能。而是根据检索算法这个例子来学习时间复杂度的定义学会计算时间复杂度。
