前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >复杂度O

复杂度O

作者头像
小小杨
发布于 2021-10-13 02:35:05
发布于 2021-10-13 02:35:05
4350
举报
文章被收录于专栏:下落木下落木

1. big O的含义

在学术界,严格地讲,O(f(n))表示算法执行的上界。比如,归并排序算法的时间复杂度是O(nlogn)的,同时也是O(n^2)

在业界,我们就是用O来表示算法执行的最低上界。所以,我们一般不会说归并排序是O(n^2)的。

2. 例题:

有一个字符串数组,将数组中的每一个字符串按照字母序排序;之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度?

错误答案:O(n*nlogn + nlogn) = O(n^2logn)

正确解答:

假设最长的字符串长度为s;数组中有n个字符串 对着每个字符串排序:O(slogs) 将数组中的每一个字符串按照字母序排序:O(n*slog(s)) 将整个字符串数组按照字典序排序:O(s*nlog(n)) 所以:O(n*slog(s)) + O(s*nlog(n)) = O(n*s*logs + s*n*logn) = O(n*s*(logs+logn)) 整数比较是O(1),字符串的字典序比较是O(s), 所以整个字符串数组进行字典序排序是O(s*nlog(n))。

3. 如果要想在1s之内解决问题:

(1)O(n^2)的算法可以处理大约10^4级别的数据;

(2)O(n)的算法可以处理大约10^8级别的数据;

(3)O(nlogn)的算法可以处理大约10^7级别的数据;

递归调用有空间代价,一般递归深度有多少,占用的空间就有多少。

4. 下面程序是O(n^2)的吗?

30n次基本操作:O(n)

5. O(logn)

二分查找法的时间复杂度是O(logn)的

不要看到for循环,就认为是一层O(n),下面是两个例子

例1:

不是O(n^2),而应该是O(nlog(n))。

例2:

是O(sqrt(n))。

再来看一下O(logn)的效率:

log2*N / logN = (log2 + logN) / logN = 1 + log2/logN

如果数据规模增加两倍,当数据量很大的时候,后面的一项可以忽略不计,也就是说运行时间几乎没有增长。

从而可以得知:

1.如果可以将顺序查找的问题转成二分查找的问题,那么就能大大提升效率。

2.O(n)和O(logn)有本质差别,同理,O(n^2)和O(nlogn)也有本质差别。

6. 递归

6.1 递归中进行一次递归调用的复杂度分析:

时间复杂度:O(logn)

如果递归函数中,只进行一次递归调用,递归深度为depth;在每个递归函数中,时间复杂度为T;则总体的时间复杂度为O(T*depth)。

例题:

根据前面O(logn)的性质,可知上面的幂运算比O(n)快很多。

6.2 递归中进行多次调用,以两次调用为例:

上面函数和归并排序不同,归并排序每次递归数据量都有减少,也就是分治算法。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 下落木 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
看动画轻松理解时间复杂度(二)
上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm time complexity),最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均时间复杂度(average case time complexity)和均摊时间复杂度(amortized time complexity)。
五分钟学算法
2018/12/25
6380
究竟什么是时间复杂度,怎么求时间复杂度,看这一篇就够了
我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每个单元运行消耗的时间都是相同的。
代码随想录
2020/06/12
4.2K0
排序-归并排序,一种外排序,递归,非递归,磁盘?
归并排序是一种分治思想的应用,所以也适合处理大数量的排序,因此也是一种外排序算法,磁盘排序算法,应用场景也较多,比如mysql的排序,sharding-jdbc的排序,
阿伟
2019/10/14
1.2K0
小米嵌入式软件工程师笔试题目解析
2.某二叉树的中序遍历序列为32145,后序遍历序列为32145,则前序遍历序列为
嵌入式与Linux那些事
2021/04/20
9950
数据结构与算法 --- 排序算法(二)
上一篇数据结构与算法 --- 排序算法(一)中,学习了冒泡排序,插入排序,选择排序这三种时间复杂度为
Niuery Diary
2023/10/22
3180
数据结构与算法 --- 排序算法(二)
前端学数据结构与算法(一):不会复杂度分析,算法等于白学
兜兜转转了这么久,数据结构与算法始终是逃不过命题。曾几何时,前端学习数据结构与算法,想必会被认为不务正业,但现今想必大家已有耳闻与经历,面试遇到链表、树、爬楼梯、三数之和等题目已经屡见不鲜。想进靠谱大厂算法与数据结构应该不止是提上日程那么简单,可能现在已经是迫在眉睫。这次决定再写一个系列也只是作为我这段时间的学习报告,也不绝对不会再像我之前的vue原理解析那般断更了,欢迎大家监督~
飞跃疯人院
2020/10/07
9340
冰与火之歌:「时间」与「空间」复杂度
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽然结果相同,但在过程中消耗的资源和时间却会有很大的区别,比如快速排序与猴子排序:)。
五分钟学算法
2018/12/25
7280
时间复杂度o(1), o(n), o(logn), o(nlogn)
1、时间复杂度o(1), o(n), o(logn), o(nlogn)。算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn),这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
别先生
2019/10/15
1.5K0
递归的时间复杂度(Master 公式)
我们在解决算法问题时,经常会用到递归。递归在较难理解的同时,其算法的复杂度也不是很方便计算。而为了较为简便地评估递归的算法复杂度,Master公式。
code张
2024/03/12
2200
十大经典排序算法 -- 动图讲解
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
互扯程序
2019/06/14
1.4K0
数据结构_时空复杂度
两个for循环里的条件判断都是<=n,处理都是++ 第一层循环执行次数是n,第一层下第二层循环是n-2^i^ 所以是O(n^2^)
用户10551528
2023/05/09
2390
数据结构_时空复杂度
归并排序 O(nLogn)
归并排序的思想是分治法+回溯,将一个无序的数组先按照原来的一半进行拆分,一直拆分到最后一个元素,然后开始回溯,排序开始的过程是再回溯时开始排序的。
g小志
2020/07/21
4140
如何实现归并排序?
划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。
行百里er
2020/12/02
5730
如何实现归并排序?
【数据结构与算法】十大经典排序算法深度解析:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序
这个序列是逐渐减小的,gap的值较大时,数据可以更快的前后变动,但不容易"基本有序";gap较小时数据前后变动较慢,但更接近"基本有序"。 通常可以选取gap = n/3, gap = gap/3, ...,直到gap= 1。
倔强的石头_
2024/12/06
1.6K0
【数据结构与算法】十大经典排序算法深度解析:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序
数据结构与算法:复杂度
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
用户11029103
2024/03/19
1660
数据结构与算法:复杂度
数据结构初阶——算法复杂度超详解
数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用,所以我们要学各式各样的数据结构, 如:线性表、树、图、哈希等
fhvyxyci
2024/09/24
1980
数据结构初阶——算法复杂度超详解
看动画轻松理解时间复杂度(一)
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽然结果相同,但在过程中消耗的资源和时间却会有很大的区别,比如快速排序与猴子排序:)。
五分钟学算法
2018/12/25
5720
数据结构——时间复杂度和空间复杂度
在大O表示法中,logn一般指的是以2为底的对数,因为绝大部分都只用考虑二分的情况,以其他数为底的情况很少出现。
HZzzzzLu
2024/11/26
5150
数据结构——时间复杂度和空间复杂度
经典排序算法和python详解(三)
经典排序算法和python详解(三):归并排序、快速排序、堆排序、计数排序、桶排序和基数排序
Minerva
2020/05/21
4860
【排序算法】 归并排序详解!深入理解!思想+源码实现!
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
屿小夏
2024/01/22
6910
【排序算法】 归并排序详解!深入理解!思想+源码实现!
推荐阅读
相关推荐
看动画轻松理解时间复杂度(二)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档