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

2024-03-14 17:44

本文主要是介绍算法时空复杂度分析:大O表示法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 大O表示法
  • 3个时间复杂度分析原则
  • 常见的时间复杂度量级
  • 空间复杂度
  • 参考资料

前言

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

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

  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 timefor i in range(n):  # n个unit timea += i  # n个unit timereturn 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 timefor i in range(n):  # n个unit timefor j in range(n): # n^2个unit timea += i*j  # n^2个unit timereturn a

用一个公式表示就是:
在这里插入图片描述
其中:

  • 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 timefor i in range(n):  # n个unit timea += i  # n个unit timereturn a

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

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

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

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

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

常见的时间复杂度量级

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

在这里插入图片描述
在这里插入图片描述

空间复杂度

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

举个栗子🌰,空间复杂度为 O ( n ) O(n) O(n)

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

参考资料

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

这篇关于算法时空复杂度分析:大O表示法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/809192

相关文章

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景