算法的时间复杂度
2007年12月02日 星期日 01:17
定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数
T(n)称为这一算法的“时间复杂性”。
当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我
们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立
f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。
此外,一个问题本身也有它的复杂性,
如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。
“大O记法”:在这种描述中使用的基本参数是
n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是
O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当
n增大时,运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能
造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的
O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。
O(1)
Temp=i;i=j;j=temp;
以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作
T(n)=O(1)。如果算法的执行时
间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
O(n^2)
2.1. 交换i和j的内容
sum=0; (一次)
for(i=1;i<=n;i++) (n次 )
for(j=1;j<=n;j++) (n^2次 )
sum++; (n^2次 )
解:T(n)=2n^2+n+1
=O(n^2)
2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解: 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).
O(n)
2.3.
a=0;
b=1; ①
for
(i=1;i<=n;i++) ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解: 语句1的频度:2,
语句2的频度: n,
语句3的频度: n-1,
语句4的频度:n-1,
语句5的频度:n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n )
2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解:
语句1的频度是1,
设语句2的频度是f(n),
则:2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )
O(n^3)
2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 ,
所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了:
0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).
我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2),但期望时间是
O(nlogn)。通过每次都仔细 地选择基准值,我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于
0。在实际中,精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法:
访问数组中的元
素是常数时间操作,或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素,如二分检索,通常它就取
O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3),因为算出每个元素都需要将n对
元素相乘并加到一起,所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如,n个元
素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了,除非n的值非常小,因为,在
这个问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题 (如著名 的“巡回售货员问题”
),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况, 通常应该用寻找近似最佳结果的算法替代之。
http://blog.chinaunix.net/u/26481/showart_479537.html
分享到:
相关推荐
算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
时间复杂度计算 首先了解一下几个概念。一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法 的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时 ,该算法时间复杂度的数量级。 ...
数据结构预算法——时间复杂度分析实例课件 数据结构预算法.pdf
本文将深入探讨时间复杂度的相关知识,包括其定义、分类、计算方法以及比较方法,并通过实例分析其在实际应用中的重要性。 时间复杂度是一个函数,它描述了算法执行时间与输入规模之间的关系。通常,我们使用大O...
好不容易找到的~超详细..相信看了之后都能战胜时间复杂度这个难题!
对资源的描述: 该资源提供了时间复杂度的基本概念,包括大O表示法,以及如何计算和比较不同算法的时间复杂度。它通过实例分析,展示了如何评估常见算法(如排序和搜索算法)的性能,并指导如何根据实际应用场景选择...
针对经典算法求最大积实例的时间复杂度高,提出新算法来求解该问题。该算法将求贝叶斯网络的最大积实例问题转变成一组一元一次方程,而一元一次方程很容易求解;通过临时表来缓存计算最大积概率时的中间结果,而这些...
1.算法效率 2.时间复杂度 3.空间复杂度 1.算法效率 2.时间复杂度 1. 实例1基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N
这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。 ...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
介绍了增量决策树算法的基本原理,并从实例费用和信息熵费用两个角度出发,对增量决策树算法的复杂度进行分析.通过实例说明,增量决策树算法能够构造出与ID3 算法形态基本相同的决策树.
但是在大数据处理问题上有绝对的速度优势 假设数据量为n 对于运行次数 (不是时间复杂度)遍历算法可能是n的n次方或者 n的阶乘 动态规划至少也是n的三次方 遗传算法大概也就几百乘 n的平方 大数据通常是亿为单位的
响 主要有两方面 一是对结果好坏的影响 二是对计算复杂度的影响 。 2. 概率常数设置 接下来就是概率常数的设置。 一是染色体杂交时所设置的概率,二是 染色体变异时所设置 的概率 。 概率设置的不同对算法的收敛快慢...
本算法比较清晰,易读。运行后自动出结果。 背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优...
针对不完备决策表,黄兵给出一种基于容差关系的相容矩阵的属性约算法,但算法比较费时,其时间复杂度为[O(|C|3|U|2)]。为降低原算法的时间复杂度,以矩阵距离为启发信息,并运用矩阵合取的特性,设计了一个新的属性...
新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息,结合基数排序,使得算法最终时间复杂度为[O(|C||U|2)],相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)],时间复杂度有效降低。通过实例说明了新算法的正确...
在决策表中,为了评价某条件属性的重要性,不但要考虑这个属性...该方法能够较快地获得可分辨矩阵,并直接求出属性集的依赖度,从而大大降低了算法的时间复杂度.实例验证了该方法具有较好的有效性和较低的时间复杂度.
在决策表中,为了评价某条件属性的重要性,不但要考虑这个属性...该方法能够较快地获得分辨矩阵,并直接求出属性集的依赖度,从而大大降低了算法的时间复杂度。实例验证了该方法具有较好的有效性和较低的时间复杂度。
首先通过图表比较不同排序算法的时间复杂度和稳定性。 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入排序 O(n2) O(n2) O(n) O(1) 是 冒泡排序 O(n2) O(n2) O(n...