首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【从0到1学算法】大O表示法

【从0到1学算法】大O表示法

作者头像
KEN DO EVERTHING
发布于 2020-07-24 08:18:19
发布于 2020-07-24 08:18:19
85600
代码可运行
举报
文章被收录于专栏:KEN DO EVERTHINGKEN DO EVERTHING
运行总次数:0
代码可运行

一般我们在选择算法时,都是想要选择效率最高的算法。那算法的效率,用什么表示?没错!就是用大O表示法。

PS: 大O表示法中,log即为log2,后面不再说明。

下面以简单查找和二分查找,在含有n个元素的有序列表中查找其中一个元素为例,下表总结了我们发现的情况。

使用简单查找时,最多需要猜测次数与列表长度相同,这被称为线性时间,大O表示法为O(n)。

二分查找则不同,最多需要猜测次数为logn(n为列表长度),这被称为对数时间(log时间),大O表示法为O(logn)。

基本概念

大O表示法指出了算法的速度有多快。

可能你会好奇,它的单位是多少?秒?没有单位,它并非指的是时间,而是从增量的角度衡量。

列表中查找元素,简单查找、二分查找的增速如下图。

假若我们不知道增速,只知道查找100个元素时的查找时间,猜测10000个元素时的查找时间:

对于简单查找,100个元素时为100毫秒,简单推算出10000个元素为10秒;

对于二分查找,100个元素时为7毫秒,简单推算出10000个元素为700毫秒。

PS:简单推算 10000个元素时的运行时间= 运行时间(100个元素时)* 100

简单查找的推算是对的,因为的增速是n,而二分查找的推算是错的,它的增速为logn,这便不能理所当然简单推算了。

很显然,我们只要知道算法的增速,便能知道它在n个元素中运行的运行时间了,大O表示法就是用来表示算法增速的。

专业描述:大O表示法表示操作数的增速,指出了算法运行时间的增速。

常见的大O运行时间(从快到慢)
  • O(㏒n) 对数时间 比如二分查找
  • O(n) 线性时间 比如简单查找
  • O(n*㏒n) 比如快速排序
  • O(n²) 比如选择排序
  • O(n!) 比如旅行者问题
大O表示法的不同维度
时间复杂度

上述的大O表示法都是用来表示时间复杂度,而且通常指的是最坏情况下的时间复杂度。

通常有以下3种时间复杂度:

以简单查找为例子,在n个元素的列表中查找目标元素

  • 最好情况时间复杂度:目标元素刚好在列表第一个位置,那么只需要一次就能找到,时间复杂度为O(1)。
  • 最坏情况时间复杂度:目标元素在列表最后一个位置或者不在列表中,那么得需要遍历完整个列表才能得出结果,时间复杂度为O(n)。
  • 平均情况时间复杂度:考虑目标元素在列表中任何位置的情况。 下面简单分析下:目标元素如果在列表中,出现的位置有n种情况,加上不在列表中这一种情况,总共n+1种情况。每种情况下需要遍历的次数如下表: 目标元素所在位置 遍历次数 第1个位置 1 第2个位置 2第3个位置 3第n个位置 n 不在列表中 n 平均遍历次数=各种情况遍历次数相加÷总的情况数 各种情况遍历次数相加为((1+2+3...+n)+n),总的情况数(n+1)

平均情况复杂度为:

((1+2+3...+n)+n)/(n+1)=n(n+3)\2(n+1)

大O表示法,会省略系数、低阶、常量,所以平均情况时间复杂度是O(n)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,反映的是一个趋势。

空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)。

例子:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 O(1)。

空间复杂度 O(n)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

第一行new了一个长度为n的数组m,占用大小为n,后面虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即O(n)。

PS:O(n²)的异同,不再累述。

以下常见排序算法的复杂度分析,感受一下时间复杂度和空间复杂度。

参考:《算法图解》 https://blog.csdn.net/jsjwk/article/details/84315770

https://www.cnblogs.com/jonins/p/9956752.html

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

本文分享自 KEN DO EVERTHING 微信公众号,前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
排序算法(二)
归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。提到分而治之一般就需要用到递归。
多云转晴
2020/04/10
4610
排序算法(二)
数据结构(二)之算法基础
  一.为什么要学习算法?     先来个简单的算法比较:求sum=1+2+3+...+(n-1)+n的结果. 输入整数n,输出 sum        解法一:for循环   function sum(n){ var s=0;            //执行1次 for(var i=1;i<n+1;i++){    s+=i;           //执行n+1次      }       解法二: function sum(n){ re
用户2145235
2018/05/18
6550
算法:时间复杂度+二分查找法(Java/Go/Python)实现
曾几何时学好数据结构与算法是我们从事计算机相关工作的基本前提,然而现在很多程序员从事的工作都是在用高级程序设计语言(如Java)开发业务代码,久而久之,对于数据结构和算法就变得有些陌生了,由于长年累月的码砖的缘故,导致我们都快没有这方面的意识了,虽然这种论断对于一些平时特别注重学习和思考的人来说不太适用,但的确是有这样的一个现象。
用户5927304
2019/07/31
5440
【初阶数据结构】算法复杂度
对于我们所要解决的问题来说,解决的方法各有不同,每个人各有各的道理,并且受制于所用的设备的性能环境不同,我们很难精确比较一些方法不太明显的差别,因此,如何脱离环境直接衡量一个算法本身的好坏呢?比如对于以下斐波那契数列:
ZLRRLZ
2024/12/13
1600
【初阶数据结构】算法复杂度
前端学数据结构与算法(一):不会复杂度分析,算法等于白学
兜兜转转了这么久,数据结构与算法始终是逃不过命题。曾几何时,前端学习数据结构与算法,想必会被认为不务正业,但现今想必大家已有耳闻与经历,面试遇到链表、树、爬楼梯、三数之和等题目已经屡见不鲜。想进靠谱大厂算法与数据结构应该不止是提上日程那么简单,可能现在已经是迫在眉睫。这次决定再写一个系列也只是作为我这段时间的学习报告,也不绝对不会再像我之前的vue原理解析那般断更了,欢迎大家监督~
飞跃疯人院
2020/10/07
9580
每日一问之算法的时间复杂度
这周调整了下计划,鉴于很多不懂的知识需要大量的时间去消化及整理输出,因此,改为每逢节假日更新每日一问。
caoqi95
2019/03/28
6820
简单复习下前端算法复杂度相关的知识
大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。
前端达人
2021/09/08
3460
文心一言 VS chatgpt (5)-- 算法导论2.2 3~4题
# 三、再次考虑线性查找问题(参见练习 2.1-3)。假定要查找的元素等可能地为数组中的任意元素,平均需要检查输入序列的多少元素?最坏情况又如何呢?用0记号给出线性查找的平均情况和最坏情况运行时间。证
福大大架构师每日一题
2023/06/08
1770
文心一言 VS chatgpt (5)-- 算法导论2.2 3~4题
02 复杂度分析_pythoner学习数据结构与算法系列
设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度。
诡途
2020/10/16
5680
02 复杂度分析_pythoner学习数据结构与算法系列
【数据结构】时间复杂度
⒉其次能够使用一种语言熟练的实现这些数据结构。一般在项目开发当中,我们是不需要自己实现数据结构的、一般成熟的面向对象都有自己的数据结构库、如C++的STL(C++算法当中的库),Java的集合类。但是造轮子是一个深度的学习过程,经过这样的学习,你对数据结构的理解就脱胎换骨了,能够更加高效的使用他们。其次技术进阶的一个必经之路就是学习开源的项目,很多的开源项目都用了很多的数据结构,数据结构不扎实的话就相当于技术进阶的拦路虎。
謓泽
2023/10/16
1810
【数据结构】时间复杂度
算法01-算法概念与描述
本系列为C++算法学习系列,会介绍 算法概念与描述,入门算法,基础算法,数值处理算法,排序算法,搜索算法,图论算法, 动态规划等相关内容。本文为C+算法概念与描述部分。
IT从业者张某某
2023/10/16
2580
算法01-算法概念与描述
学习前端算法前你需要了解的‘大O表示法’
在现实生活中,解决一个问题可以有多种方法,其中有好的方法,也有较为一般的方法。评判标准虽有不同,但总体思想是:用最小的代价获得最多的收益。
前端迷
2020/07/03
8360
学习前端算法前你需要了解的‘大O表示法’
【数据结构】复杂度讲解
数据结构中是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合.
IT编程爱好者
2023/04/12
2890
【数据结构】复杂度讲解
数据结构与算法:复杂度
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
用户11029103
2024/03/19
1940
数据结构与算法:复杂度
算法图解2-二分法和选择排序
二分法查找 猜数字游戏 0-1000猜数字游戏: 普通查找:100,99,98,…,1,需要100步 二分法查找:100--->50--->25--->13--->7--->4--->2--->1,每次猜测中间的数字(假设猜测数字是1),将余下的数字排除一半。需要7步 n个元素组成的列表,最多需要走log_2{n}步。普通查找n步 attention:二分法查找仅对有序列表有用 思想 折半查找,比较次数少,速度快,只能作用于有序数组和顺序表,当查找范围内只有一个数据的时候,结束查找。
皮大大
2021/03/02
7200
算法—时间复杂度[通俗易懂]
时间和空间都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少;
全栈程序员站长
2022/08/27
3.3K0
算法—时间复杂度[通俗易懂]
算法的时间复杂度和空间复杂度计算
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,是一种“渐进表示法”。其中f(n)是问题规模n的某个函数。
全栈程序员站长
2022/08/28
3.7K0
算法的时间复杂度和空间复杂度计算
【初阶数据结构】——时间复杂度和空间复杂度详解(C描述)
我们已经了解了什么是算法,那当我们写出一个算法的时候,如何去衡量这个算法的好坏呢?
YIN_尹
2024/01/23
4440
【初阶数据结构】——时间复杂度和空间复杂度详解(C描述)
C语言---数据结构(1)--时间复杂和空间复杂度计算
时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度,现在主要关注的是空间效率
Undoom
2024/09/23
1520
C语言---数据结构(1)--时间复杂和空间复杂度计算
数据结构初步(一)- 时间与空间复杂度
当当当,本节开始进入到数据结构的学习之旅。什么是数据结构呢,什么又是时间复杂度与空间复杂度呢?学习数据结构的道路并不是一帆风顺的,唯有持续冲锋数据结构的高地。
怠惰的未禾
2023/04/27
6110
数据结构初步(一)- 时间与空间复杂度
相关推荐
排序算法(二)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档