浅谈时间复杂度- 算法衡量标准Big O
写在前面:
今天有一场考试,考到了Big-O的知识点,考到了一道原题,原题的答案我记住了,但实际题目有一些改动导致答案有所改动,为此作者决定重新整理一下复杂度相关知识点
Efficiency and Complexity。
我觉得的学习Big-O之前有必要先了解一下以下这些知识,其中大部分翻译自我们老师的课件,也有一部分自己理解加入,如果有专业名词翻译错误欢迎指正!
- 时间复杂度与空间复杂度
在写程序的时候,我们通常需要判断某一个算法或者程序是否可以完成某一项任务。拿12306的铁路订票系统举例,如果完成一次订票需要半个小时或者更久,这是很难被用户认可或者接受的。所以保证等待时间的合理是非常必要的(当然越短越好)。我们将一个算法的时间复杂度作为一个指标,而最终执行时间取决于数据结构的大小。
另一个效率指标就是一个程序需要多少空间去来执行特定任务,但是这个指标在现代的计算机我们考虑的很少。我们一般可以认为空间复杂度取决于数据结构的大小。
我们会发现,作为一个数据存储设备,哈希表有一个很好的时间复杂度为,但代价是会比其它算法使用更多的内存。所以两个复杂度通常是由算法/程序员决定如何最好地为程序平衡取舍
- 最差和平均复杂度(worst versus average complexity)
另一个很重要的指标就是平均复杂度,有的情况下,平均复杂度要比最差复杂度要重要很多。比如一个日常的软件,这里拿我们经常使用的操作系统Windows来举例子,即使经常死机(此时是最差的情况),只要保证在大部分情况下可以正常的运行就可以,也就是说可以为了保证平均的复杂度比保证最坏情况运行更加重要。而在另外一些情况下,比如录音软件,为了采集连续数据,需要考虑时效性,它完全不能接受软件等待时间太长,这样采集数据就不会连续,录音就会不完整。
而这些也是通过具体的例子来进行权衡的。
- 具体的性能指标
大多数情况,我们感兴趣的是时间复杂度(time complexity)也就是经常提到的Big-O,因此我们需要了解怎么计算它。一个人可能写了一个程序并且运行,并且看看这个程序运行了多长时间,但是这个程序可能会发生一些意想不到的错误,尤其是对于大型的程序,可能每次运行由于不同的条件会发生很大的变化,并且同样程序会因为处理器,或者数据量,读写速度等很多条件下不同,因此时间并不能很好的衡量一个程序或者算法的性能。而复杂度是最好的方式来衡量一个算法/程序,我们可以用伪代码来计算复杂度,由于伪代码很接近我们写程序,并且不需要花费大部分时间来完成程序(我们的任务不就是来计算时间复杂度吗,所以不需要花费太多时间来计算时间复杂度)
Big O notation
Big O notation是一种描述述函数渐进行为的理论,又被称作Landau’s symbol,其实这部分是高数中的概念。用于表述一个函数增长的多快或者减少的多快。(重点描述加速度),在计算机领域,Big O notation常常用来表达算法时间复杂度和性能的术语,一个算法在执行过程中需要的最大时间或者最大空间。
那么为什么要用O来表示呢?
大O符号是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作《解析数论》(Analytische Zahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道(Edmund Landau)的著作中才推广的,因此它有时又称为朗道符号(Landau symbol)。代表“order of …”(……阶)的大O,最初是一个大写的希腊字母’Θ’(Omicron),现今用的是英文大写字母’O’,但从来不是阿拉伯数字’0’。
最常见的几种复杂度类型(升序排列)
O(1):常数,结果是相同的,输入值不影响时间(空间),
O(loglogn),
O(logn):对数,经典算法:二叉搜索树(AVL数)查找算法,
O(n), 线性,表示随着输入的增加,所需的执行时间(空间)也线性增加,
O(nlogn),
O(n^2),
O(n^3),
O(2^n )
....
我们可以观察不同n值下面具体复杂度的值。
显示在坐标中会更加明显
那么问题是:如何计算呢?
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
例如:
O(n^2 + 4n + 1) 受 n^2影响最大,于是二次方程我们记为O(n^2)
同理:
O(2n^3 + n^2 + 1) = O(n^3)(此处=不知是否妥当,欢迎网友指正)
O(n+4logn) = O(n)
这里我们引入T(n)概念,时间复杂度的表示法T(n)=O(f(n)) 其中f(n)一般是算法中频度最大的语句频度
例如:
1.数组遍历
for(int i = 0; i < a.length; i++){ system.out.print(a[i]+" ") }
很明显遍历数组元素个数n次 也就是说f(n) = n,
那么T(n) = O(n)
2.查看数组中是否有重复元素
for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (a[i]==a[j]) { eturn true; } } } return false;
分析:
对于第一个for循环,0<i<n,最坏的情况下有n次;分别是n=0,1,2...i...n-1.
对于第二个for循环,i+1<j<n, 最坏的情况下有 n-i-1次,将0<i<n以此代入
即 n-1, n-2, n-3....n-i-1....0
相加便是n(n-1)/2次运算 即f(n) = n(n-1)/2
那么T(n) = O(n(n-1)/2)也就是T(n) = O(n^2)
以上是完整的分析方式,但是对于算法来说,我们通常不会如此细致的去分析,因为本来复杂度都是取的最坏的情况 因此我们只需要估算。
3.
i = 1; while(i <= n){ i = i*2 }
我们可以看到 执行f(n)次
也就是2^f(n) <= n
f(n) = log2 n
T(n) = O(f(n)) = O(logn) (这里通常会把log2 n记为 logn)
声明:
本文70%原创, 30%摘抄整理翻译
引用:
http://blog.csdn.net/firefly_2002/article/details/8008987
http://blog.csdn.net/iluna/article/details/4159485
http://www.ehcoo.com/complexity.html
最新文章
- python numpy包
- mac攻略(七) -- 环境变量PATH分析
- Sql Server 2008R2 遇到了BCP导入各种中文乱码的问题
- Windows性能计数器2
- c++命名空间瀑布
- Oracle中使用escape关键字实现like匹配特殊字符,以及&;字符的转义
- C#多线程的用法3-线程间的协作Join
- .Net Core版开源跨平台框架SkyMallCore
- jq修改hover样式
- PHP中使用CURL之php curl详细解析
- Java基础之一
- 深度学习Tensorflow生产环境部署(上&#183;环境准备篇)
- 环境部署(九):linux下安装python+chrome+Xvfb
- phpstorm显示页面不停的在indexing转圈中,并且文件名还一直在刷新
- LeetCode-52.N-Queen II
- python --- 19 判断对象所属,区分函数和对象, 反射
- 解决Kubernetes 1.7.3 kube-apiserver频繁异常重启的问题(转)
- 图解Ajax工作原理
- python判断unicode是否是汉字,数字,英文,或者其他字符
- 2018JAVA复习摘要
热门文章
- (中等) POJ 2948 Martian Mining,DP。
- uartz Spring与Spring Task总结
- width这样读取出来是一个字符串,并且带有单位,但是offsetwidth返回的是一个数值。
- S3C2440的RTC解析
- AndroidStudio项目.gitignore文件内容
- 如何在我自己的web 项目的jsp页面中添加链接,直接让别人通过内网在我的电脑上下载文件
- stm32 DMA数据搬运 [操作寄存器+库函数](转)
- IOS三种归档(NSKeyArchieve)的总结
- Ubuntu上搭建Git服务器
- bitmap资源回收