算法复杂度
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法复杂度,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1798字,纯文字阅读大概需要3分钟。
内容图文
一,时间复杂度
通常我们也不需要知道T(n)的确切大小,而只需要对其上界作出估计。比如说,如果存在正常数a、N 和一个函数f(n),使得对于任何n > N,都有
T(n) < a × f(n)
我们就可以认为在n 足够大之后,f(n)给出了T(n)的一个上界。对于这种情况,我们记之为
T(n) = O(f(n))
这里的O 称作“大O 记号(Big-O notation)”。
如果存在正常数a、N 和一个函数g(n),使得对于任何n > N,都有
T(n) > a × g(n)
我们就可以认为在n 足够大之后,g(n)给出了T(n)的一个下界。对于这种情况,我们记之为
T(n) = Ω(g(n))
这里的Ω称作“大Ω记号(Big-Ω notation)”。
二,空间复杂度
衡量算法性能的另一个重要方面,就是算法所需使用的存储空间量,即算法空间复杂度。显然,对于同样的输入规模,在时间复杂度相同的前提下,我们希望算法所占用的空间越少越好。不过,在通常情况下,我们将更多地分析和讨论算法的时间复杂度,甚至只关注时间复杂度。之所以能够这样做,是基于以下事实:
就渐进复杂度的意义而言,在任何一个算法的任何一次运行过程中,其实际占用的存储空间都不会多于其间执行的基本操作次数。
O(1):具有常数的时间复杂度
算法:NonextremeElement(S[], n)
输入:由n个整数构成的集合S
输出:其中的任一非极端元素
{
任取的三个元素x, y, z ∈ S; //既然S是集合,这三个元素必互异
通过比较,找出其中的最小者min{x, y, z}和最大者max{x, y, z};
输出最小、最大者之外的那个元素;
}
既然S 是有限集,故其中的最大、最小元素各有且仅有一个。因此,无论S 的规模有多大,在前三个元素S[0]、S[1]和S[2]中,必包含至少一个非极端元素。于是,我们可以取x =S[0]、y = S[1]和z = S[2],这只需执行三次基本操作,耗费O(3)时间。接下来,为了确定这三个元素的大小次序,我们最多需要做三次比较(请读者自己给出证明),也是O(3)时间。最后,输出居中的那个元素只需O(1)时间。综合起来,算法一.4 的运行时间为:
T(n) = O(3) + O(3) + O(1) = O(7) = O(1)
O(logn): 具有对数的时间复杂度
算法:BaseConversion(n)
输入:十进制整数n
输出:n的三进制表示
{
不断循环,直到n = 0 {
输出 n mod 3; //取模
令 n = n/3; //整除
}
}
每一轮循环内部,都只需进行两次基本操作(取模、整除)。为了确定需要进行的循环轮数,我们可以注意到以下事实:每经过一轮循环,n都至少减少至1/3。于是,至多经过1+?log3n?次循环,即可减小至0。因此,该算法需要运行O(2×(1+?log3n?)) = O(log3n)时间。
鉴于大O 记号的性质,我们通常会忽略对数函数的常底数。比如这里的底数为常数3,故通常将上述复杂度记作O(logn)
O(n) : 具有线性时间复杂度
算法:Sum(A[], n)
输入:由n个整数组成的数组A[]
输出:A[]中所有元素的总和
{
令s = 0;
对于每一个A[i],i = 0, 1, …, n-1
令s = s + A[i];
输出s;
}
对s的初始化需要O(1)时间。算法的主体部分是一个循环,每一轮循环中只需进行一次累加运算,这属于基本操作,可以在O(1)时间内完成。每经过一轮循环,都对一个元素进行累加,故总共需要做n轮循环。因此,算法一.6 的运行时间为
O(1) + O(1)×n = O(n+1) = O(n)
O(n^2) : 具有平方时间复杂度
算法:Bubblesort(S[], n)
输入:n个元素组成的一个序列S[],每个元素由[0..n-1]之间的下标确定,元素之间可以比较大小
输出:重新调整S[]中元素的次序,使得它们按照非降次序排列
{
从S[0]和S[1]开始,依次检查每一对相邻的元素;
只要它们位置颠倒,则交换其位置;
反复执行上述操作,直到每一对相邻元素的次序都符合要求;
}
原文:http://www.cnblogs.com/IvySue/p/7479510.html
内容总结
以上是互联网集市为您收集整理的算法复杂度全部内容,希望文章能够帮你解决算法复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。