算法时空复杂度分析:大O表示法

这篇具有很好参考价值的文章主要介绍了算法时空复杂度分析:大O表示法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

算法题写完以后,面试官经常会追问一下你这个算法的时空复杂度是多少?(好像作为一名算法工程师,我日常码代码的过程中,并没有太注意这个,惭愧~但是找做后端开发的男票求证了一下,他们日常工作确实会去考虑这种问题)那么无论是为了应付面试,还是为了未来码代码可以精益求精,都还是认真的学一下时空复杂度分析方法吧!

对于为什么需要时空复杂度分析,而不是直接跑一下代码看看,看到王争大佬在《数据结构与算法之美》(墙推)里给的两个原因是:

  1. 测试结果依赖测试环境:机器的配置会十分影响你跑出的结果;
  2. 测试结果依赖数据规模的大小。

因此,我们需要一个不依赖数据规模和测试环境,帮助粗略估计算法执行效率的方法!也就是下面的大O表示法~

大O表示法

举个栗子🌰,下面这个函数的总的执行时间 T ( n ) = 1 + 2 n T(n) = 1+2n T(n)=1+2n个unit time!

def f(n: int)
	a = 0  # 1个unit time
	for i in range(n):  # n个unit time
		a += i  # n个unit time
	return a

再举个栗子🌰,下面这个函数的总的执行时间 T ( n ) = 1 + n + 2 n 2 T(n) = 1+n+2n^2 T(n)=1+n+2n2个unit time!

def g(n: int, m: int)
	a = 0  # 1个unit time
	for i in range(n):  # n个unit time
		for j in range(n): # n^2个unit time
			a += i*j  # n^2个unit time
	return a

用一个公式表示就是:
算法时空复杂度分析:大O表示法,Python,LeetCode,算法,python,笔记
其中:

  • T ( n ) T(n) T(n)表示代码执行的时间;
  • n n n:表示数据规模的大小;
  • f ( n ) f(n) f(n):表示每行代码执行的次数总和
  • O O O:表示执行时间 T ( n ) T(n) T(n) f ( n ) f(n) f(n)成正比。

所以第一个例子的时间复杂度为 T ( n ) = 1 + 2 n T(n) = 1+2n T(n)=1+2n,第二个例子的时间复杂度为 T ( n ) = 1 + n + 2 n 2 T(n) = 1+n+2n^2 T(n)=1+n+2n2,这就是大O时间复杂度表示法。大O时间复杂度表示法实际上并不是具体值代码执行的时间,而是代表代码执行时间随着数据规模增长的变化趋势,所以也叫渐进时间复杂度,简称时间复杂度。

当n很大时,公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略,只需要记录一个最大量级即可!因此,上例的时间复杂度可以记为: T ( n ) = O ( n ) T(n) = O(n) T(n)=O(n) T ( n ) = O ( n 2 ) T(n) = O(n^2) T(n)=O(n2)

3个时间复杂度分析原则

3个原则:

1. 只关注循环执行次数最多的一段代码:
还是上面第一个例子,关注for循环这段代码就行了,a = 0这类代码都是常量级的执行时间,与 n n n无关。

def f(n: int)
	a = 0  # 1个unit time
	for i in range(n):  # n个unit time
		a += i  # n个unit time
	return a

2. 总复杂度 = 量级最大的那段代码的复杂度:
这个有点像运筹学里关键路径法的思想,只有找到了最关键/量级最大的,你去优化的时候才能发力在刀刃上~

比如下面这段代码,有一层for循环的,有两层for循环,我们去关注两层for循环的这段代码即可。

def g(n: int, m: int)
   for i in range(n):
   		pass
   		 
   a = 0  # 1个unit time
   for i in range(n):  # n个unit time
   	for j in range(n): # n^2个unit time
   		a += i*j  # n^2个unit time
   return a

3. 嵌套代码的复杂度 = 嵌套内外代码复杂度的乘积:
上面的第二个例子,两层for循环嵌套,最后的时间复杂度 = 外层for循环的复杂度乘以里面for循环的复杂度。

def g(n: int, m: int)
	a = 0  # 1个unit time
	for i in range(n):  # n个unit time
		for j in range(n): # n^2个unit time
			a += i*j  # n^2个unit time
	return a

常见的时间复杂度量级

  • 多项式量级:下图左侧;
  • 非多项式量级:下图右侧波浪线。执行时间会随着数据规模的增大而急剧增大,是非常低效的算法

算法时空复杂度分析:大O表示法,Python,LeetCode,算法,python,笔记
算法时空复杂度分析:大O表示法,Python,LeetCode,算法,python,笔记

空间复杂度

又称为渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系!

举个栗子🌰,空间复杂度为 O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-842376.html

def f(n: int):
	a = 2  # 1个空间存储变量,常量
	b = [] # 从下面代码可以看出时一个大小为n的数组
	for i in range(n):
		b.append(i)
	return b

参考资料

  1. 《数据结构与算法之美》王争

到了这里,关于算法时空复杂度分析:大O表示法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法的复杂度分析

    [王有志](https://www.yuque.com/wangyouzhi-u3woi/dfhnl0/hqrch62un0cc9sp2?singleDoc# 《🔥快来关注我》),一个分享硬核Java技术的互金摸鱼侠 加入Java人的提桶跑路群:[共同富裕的Java人](https://www.yuque.com/wangyouzhi-u3woi/dfhnl0/nwry2mdlktok50bt?singleDoc# 《🔥共同富裕的Java人》) 今天我们只有一个内容:

    2024年01月23日
    浏览(29)
  • 【数据结构】算法的时间复杂度和空间复杂度(含代码分析)

    如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 这里的时间复杂度为: 2^N ,计算方法请看下文。 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复

    2024年02月05日
    浏览(59)
  • 如何分析算法的时间复杂度!

    算法时间复杂度定义 列举常见的时间复杂度以及如何计算:                           1.常数阶: 2.线性阶: 3.对数阶: 4.平方阶:         我们知道,学习数据结构和算法就是为了解决程序的“快”和“省”的问题,那么如何让代码运行得更快,让代码更省存储空间

    2024年01月16日
    浏览(46)
  • 算法与数据结构-复杂度分析

      算法的执行效率,粗略地讲,就是算法代码执行的时间。但是,如何在不运行代码的情况下,用“肉眼”得到一段代码的执行时间呢?   这里有段非常简单的代码,求 1,2,3…n 的累加和。现在,我就带你一块来估算一下这段代码的执行时间。   从 CPU 的角度来看,这

    2024年02月08日
    浏览(54)
  • 【数据结构】排序算法复杂度 及 稳定性分析 【图文详解】

    前面给大家讲述了各大排序算法的原理、思路以及实现步骤、代码码源,下面让我们来对比一下各大排序之间的算法复杂度以及稳定性分析优劣,加深我们对于各排序算法的理解,帮助我们以后能更快的在具体场景下选择出最适的排序算法。 【数据结构】冒泡排序 (码源实

    2024年02月05日
    浏览(98)
  • 数据结构英文习题解析-第一章 算法复杂度分析Algorithm Analysis

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW1 1. The major task of algorithm analysis is to an

    2024年03月12日
    浏览(71)
  • 【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

    👑专栏内容:数据结构 ⛪个人主页:子夜的星的主页 💕座右铭:日拱一卒,功不唐捐 一个程序能用很多不同的算法来实现,那么到底那种算法是效率最高的呢? 对此我们有两种方法: 第一种是事后统计法,既在编写之后,通过计时,比较不同算法编写的程序的运行时间,

    2024年02月03日
    浏览(50)
  • 【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比

    什么是算法复杂度(现实案例)? ❤️‍🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。 举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书

    2024年02月14日
    浏览(52)
  • TOP-K问题和向上调整算法和向下调整算法的时间复杂度问题的分析

    TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大 比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下

    2024年02月04日
    浏览(39)
  • 排序算法大全集,从时间复杂度和空间复杂度上对各个排序算法进一步的分析和评估,从插入排序、交换排序、归并排序、基数排序到外部排序,通晓堆排序、希尔排序、快速排序等算法

    目录 1.基本概念和排序方法概述 排序方法的分类 2.插入排序 1.直接插入排序 2.折半插入排序 3.希尔排序 3.交换排序 1.冒泡排序 2.快速排序 3.简单选择排序 4.堆排序 4.归并排序 5.基数排序 6.外部排序 7.各类排序方法的综合比较 1.时间性能 2.空间性能 3.排序方法的稳定性能 4.关于

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包