文档章节

如何理解算法时间复杂度的表示

y
 yky20190625
发布于 06/26 19:45
字数 1593
阅读 9
收藏 0

先从O(1) 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键 字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执行 该操作只需要恒定的时间(当然,实际操作中存在冲突和冲突解决的机制,不能保证每次取值的时间是完 全一样的)。举个现实的例子,比如我的身后有一排柜子,里面有香蕉(代号B),苹果(代号A),葡萄 (G),现在你说A,我迅速的就把苹果递过来了;你说B,我迅速就把香蕉递过来了。就算你再增加菠萝 (P)、火龙果(H),但是你说一个代号,我递给你相应的水果这个速度是几乎不会变的。


至于O(n) ,这个就是说随着样本数量的增加,复杂度也随之线性增加。典型的比如数数。如果一个人 从1数到100,需要100秒,那么从1到200,基本上不会小于200秒,所以数数就是一个O(n) 复杂度的 事情。一般来说,需要序贯处理的算法的复杂度,都不会低于O(n) 。比如说,如果我们要设计一个算 法从一堆杂乱的考试的卷子里面找出最高的分数,这就需要我们从头到尾看完每一份试卷,显然试卷越 多,需要的时间也越多,这就是一个O(n) 复杂度的算法。

O(n2) 是说,计算的复杂度随着样本个数的平方数增长。这个例子在算法里面,就是那一群比较挫的 排序,比如冒泡、选择等等。沿着我们刚才的说的那个试卷的例子,等我们找出最高的分数之后,放在一 边另起一堆,然后用同样的方法找第二高的分数,再放到新堆上…… 这样我们做n次,试卷就按照分数从低 到高都排好了。因为有n份试卷,第一次翻卷找最高分,要找n份试卷,第二次翻卷要找n-1份试卷,第三次翻卷要找n-2份试卷.... ,总共要找n+(n-1)+(n-2)...+1次,也就是 (n+1)n/2次,   舍去常数,就是n2次. 算法时间复杂度就是O(n2).    再比如说构建一个网络,每个点都和其他的点相连。显然,每当我们增加一个点,其实就需要构建这个点 和所有现存的点的连线,而现存的点的个数是n,所以每增加1,就需要增加n个连接,那么如果我们增加n 个点呢,那这个连接的个数自然也就是 O(n2) 量级了。

无论是翻试卷,还是创建网络,每增加一份试卷,每增加一个点,都需要给算法执行人带来n量级的工作 量,这种算法的复杂度就是 O(n2)。

然后是O(nlogn) ,这是常见算法复杂度里面相对难理解的,就是这个log怎么来的。前面那个 n,代表执行了n次 的操作,所以理解了log(n),就理解了nlog(n)。

O(logn)的算法复杂度,典型的比如二分查找。设想一堆试卷,已经从高到底按照分数排列了,我们现 在想找到有没有59分的试卷。怎么办呢?先翻到中间,把试卷堆由中间分成上下两堆,看中间这份是大于 还是小于59,如果大于,就留下上面那堆,别的丢掉,如果小于,就留下下面那堆,丢掉上面。然后按照 同样的方法,每次丢一半的试卷,直到丢无可丢为止。

具体举一个例子, 假如有32份试卷,你丢一次,还剩16份 ,丢两次,还剩下8 份,丢三次,就只剩下4份了,可以这么一直 丢下去,丢到第五次,就只剩下一份了。也就是我们一次丢一半,总要丢到只有一份的时候才能出那个要找的59分的卷子,一共执行了5次,2的5次方=32, 如果有n份,也就是大约需要log2n 次,才能得出“找到”或者“没找到”的结果。当然你说你三分查找,每次丢三 分之二可不可以?当然也可以,但是算法复杂度在这里是忽略常数的,所以不管以2为底,还是以什么数为 底,都统一的写成 的形式。

理解了这一点,就可以理解快速排序为什么是 O(nlog(n))了。比如对一堆带有序号的n本书进行排序,怎么快速排序呢?就是随便先选一本,然后把号码大于这本书的扔右边,小于这本书的扔左边。因为每本书都要比较 一次,所以这么搞一次的复杂度是O( n),那么快速排序需要我们重复多少次呢?这又回到了二分查找的逻 辑了,经过第一次后,这堆书一分为二堆,  每堆是n/2本 , 在这两堆上再重复上面的步骤, 每堆排序一次的步骤n/2次  两堆共n/2+n/2=n次 , 再两堆分四堆,每堆的步骤是n/4次, 四堆共n/4+n/4+n/4+n/4=n次....  所以每次分堆后,总的步骤次数都是n次, 请问分多少次手里每堆里只有一本书呢?答案还是log2n 。所以分堆次数是log2n ,而每分一次堆后排序总步骤是n次,因此总的次数是nlogn.也就是时间复杂度为O(nlogn).

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13594
作品 0
荆州
私信 提问
随笔:估算程序算法复杂度的理解

大体分为:事前估算(设计算法之前就估算此算法性能)和事后估算(运行后,通过收集数据) 直觉上以为是事后估算为主,毕竟,实践是检验真理的标准嘛。事后收集数据才是比较靠谱的。 不过,想法错...

wangtaotao
2014/04/10
0
0
1.数据结构&算法的引言+时间复杂度

print(sumOfN(10)) print(foo(10)) start_time = time.time()for a in range(0,1001): end_time = time.time()print(endtime-starttime) 执行结果为: 0 500 500200 375 425375 200 425500 0......

杨洪涛
06/01
0
0
数据结构与算法——学习整理记录

===注:此文由本人结合网上资源整理总结而来,仅代表个人的学习与理解,如有错漏,欢迎指正!=== # 1. 数据结构 ## 1.1 数据结构是什么? 数据结构,直白地理解,就是研究数据的逻辑关系与存...

elinuxboy
2018/11/28
0
0
算法复杂度分析(上):分析算法运行时,时间资源及空间资源的消耗

前言 算法复杂度是指算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。 复杂度也叫渐进复杂度,包括时间复杂度和空间复杂度,用来粗略分析执行效率与数据规模之间...

Jonins
2018/11/13
0
0
面试官:阮一峰版的快速排序完全是错的

面试官系列(番外): 别再使用阮一峰版的快速排序了 往期 面试官系列(1): 如何实现深克隆 面试官系列(2): Event Bus的实现 面试官系列(3): 前端路由的实现 面试官系列(4): 实现双向绑定Proxy比...

寻找海蓝96
2018/05/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

华为手机翻译功能怎么使用?这三种方法请务必收藏

华为手机翻译功能怎么使用?在我们的生活中会经常遇到翻译问题,许多外语不好的朋友该怎么办呢?华为手机已经为我们解决了这个问题,今天小编就教大家学会使用华为手机中的三种翻译技巧,需要...

翻译小天才
18分钟前
2
0
企业服务软件开发中需要注意的三个问题

在开发企业服务软件时,我们需要分为:业务需求、用户需求、产品需求,三大需求层次,三个层次互相关联,企业服务软件开发首先要服务业务,需要满足业务的需求,再关注用户体验,也就是用户需...

积木创意科技
21分钟前
2
0
C++容器底层数据结构

内置数组: int arr[10][10];memset(arr,0,10*10*sizeof(int)); //初始化int tmp[10][10];memcpy(arr, tmp, 10 * 10 * sizeof(int));//拷贝 void *memcpy(void *destin, void *source,......

SibylY
21分钟前
2
0
Dubbo-自适应拓展机制

背景 在 Dubbo 中,很多拓展都是通过 SPI 机制进行加载的,比如 Protocol、Cluster、LoadBalance 等,这些都是Dubbo的基础组件。这些基础组件的拓展不是在系统框架启动阶段被加载,而是拓展方...

rock-man
50分钟前
7
0
Kali安装fcitx输入法(五笔)

安装fcitx > sudo apt-get install fcitx-rime fcitx-config-gtk3 重启 > sudo reboot fcitx配置 效果就是这样 配置输入法切换 系统设置...

yeahlife
52分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部