来源:http://clarkluo2004.blog.163.com/blog/static/32973801200845115213422/
算法的运行时间通常与下列函数成比例:
1 | 大部分程序的大部分指令之执行一次,或者最多几次。如果一个程序的所有指令都具有这样的性质,我们说这个程序的执行时间是常数。 |
logN | 如果一个程序的运行时间是对数级的,则随着N的增大程序会渐渐慢下来,如果一个程序将一个大的问题分解成一系列更小的问题,每一步都将问题的规 模缩减成几分之一,一般就会出现这样的运行时间函数。在我们所关心的范围内,可以认为运行时间小于一个大的常数。对数的基数会影响这个常数,但改变不会太 大:当N=1000时,如果基数是10,logN等于3;如果基数是2,logN约等于10.当N=1 00 000,logN只是前值的两倍。当N时原来的两倍,logN只增长了一个常数因子:仅当从N增长到N平方时,logN才会增长到原来的两倍。 |
N | 如果程序的运行时间的线性的,很可能是这样的情况:对每个输入的元素都做了少量的处理。当N=1 000 000时,运行时间大概也就是这个数值;当N增长到原来的两倍时,运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入(或者产生N个输出), 那么这种情况是最优的。 |
NlogN | 如果某个算法将问题分解成更小的子问题,独立地解决各个子问题,最后将结果综合起来,运行时间一般就是NlogN。我们找不到一个更好的形容, 就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时,NlogN大约是20 000 000。当N增长到原来的两倍,运行时间超过原来的两倍,但超过不是太多。 |
N平方 |
如果一个算法的运行时间是二次的(quadratic),那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入 数据项的算法(在程序中很可能表现为一个嵌套循环)中,当N=1000时,运行时间是1 000 000;如果N增长到原来的两倍,则运行时间将增长到原来的四倍。 |
N三次方 | 类似的,如果一个算法需要处理输入数据想的三元组(很可能表现为三重嵌套循环),其运行时间一般就是三次的,只能用于一些规模较小的问题。当N=100时,运行时间就是1 000 000;如果N增长到原来的两倍,运行时间将会增长到原来的八倍。 |
2的N次方 | 如果一个算法的运行时间是指数级的(exponential),一般它很难在实践中使用,即使这样的算法通常是对问题的直接求解。当N=20时,运行时间是1 000 000;如果增长到原来的两倍时,运行时间将是原时间的平方! |
log log N 可以看作是一个常数:即使N很多,两次去对数之后也会变得很小
相关推荐
时间复杂度为O(logN)的常用算法,算法数据结构 五大常用算法
快速幂 基于java实现的快速幂、快速乘算法,利用二进制位运算将O(n)的算法复杂度降到O(logn)
3.1实验目的与要求 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 ...6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
这是从一位新浪网友的博客中转来的,感觉不错,就发来了,
O(logn):对数时间复杂度,表示算法的运行时间与输入数据规模n的对数成正比。 O(n):线性时间复杂度,表示算法的运行时间与输入数据规模n成正比。 O(nlogn):线性对数时间复杂度,是线性时间复杂度和对数时间...
快速排序描述:快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序...
已知(k1, k2, …, kp)是堆,则可以写一个时间复杂度为O(logn)的算法,将(k1, k2, …, kp, kp+1)调整为堆。试编写“从p=1起,逐个插入建堆”的算法,并讨论由此方法建堆的时间复杂度。
算法 大O表示法表示的运行时间 线性查找 O(N) 二分查找 O(logN) 无序数组的插入 O(1) 有序数组的插入 O(N) 无序数组的删除 O(N) 有序数组的删除 O(N) O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在...
例如,在输入数据是均匀分布时,快速排序算法所需的平均时间是O(n logn)。但是如果其输入已经基本上排好序时,所用时间就大大增加了。此时,可采用舍伍德算法消除算法所需计算时间与输入实例间的这种联系。
快速幂、快速乘算法 算法核心在于位运算,利用二进制位运算将O(n)的算法复杂度降到O(logn) 快速幂算法是一种优化的幂运算方法,它通过减少乘法的次数来加快计算速度。这种算法利用了幂运算的性质,特别是幂的...
3.1实验目的与要求 1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 ...6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
O(nlogn):表示算法的执行时间既随n的增大而增长,又随logn的增大而增长,通常出现在一些高效的排序算法中,如归并排序。 O(n²)、O(n³):表示算法的执行时间随输入规模n的平方或立方增长,通常出现在嵌套循环等...
时间复杂度为O(logN)的排序算法。。俗称重口味排序
该仓库收集一些算法的答案,目标是整理一套系统的算法参考答案以供其他学习者参考 我也在慢慢的学算法并且在坚持刷题,我会不定期的上传新的题目,希望大家共同努力! 在线编程网站: 目录 排序算法 算法 稳定 时间...
1-4在任何情况下,时间复杂度为O(n2) 的算法比时间复杂度为O(n*logn)的算法所花费的时间都长。F 1-5对n个整数排序,在最坏的情况下,不能保证以少于O(n)的时间完成。T 1-6用渐进表示法分析算法复杂度的增长...
排序算法 多种排序算法O(n * logn)
| RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA 19 | LCA 离线算法 O(E)+O(1) 20 | 带权值的并查集 20 | 快速排序 20 | 2 台机器工作调度 20 | 比较高效的大数 20 | 普通的大数运算 21 | 最长公共递增子序列 O(N^2) ...
快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)