Python算法 00--时间复杂度和空间复杂度
off999 2024-10-07 12:16 49 浏览 0 评论
通常，我们衡量一个算法的优劣，从「 时间复杂度 」和「 空间复杂度 」两个维度去考量
● 时间复杂度
执行当前算法所消耗的时间
● 空间复杂度
执行当前算法需要占用多少内存空间
「 时间复杂度 」
我们先来看一个例子：
我们通过打印程序的执行时间来看算法的「时间复杂度 」。这种栗子存在弊端，受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。
时间复杂度表示方法：「 大 O 符号表示法 」
公式：T [n] = O (f (n))
f (n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式又叫“算法的渐进时间复杂度”。
通过「 大 O 符号表示法 」，图1 的时间复杂度为：O (n)
● 常数阶 O (1)
有时候在 Python 中看到存在 ++i 这种形式，这其实不是自增，只是简单的表示正负数的正号而已。正正得正，负负得正，所以 ++i 和 --i 都是 i 。（有Java基础的老铁注意啦）
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O (1)
图2代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用 O (1) 来表示它的时间复杂度。
● 线性阶 O (n)
从最开始图1 的栗子，for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O (n) 来表示它的时间复杂度。
● 平方阶 O (n2)
如果把 O (n) 的代码再嵌套循环一遍，它的时间复杂度就是 O (n2) 了。
● 对数阶 O (logN)
① 先回顾哈 log
② 举个栗子
从图3代码中，变量i从1开始， while 循环里面，每次都将 i 乘以 2，当 i 的值大于 n 时，推出循环
也就是说当循环 log(2)(n) 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logN)
● 线性对数阶 O (nlogN)
线性对数阶 O (nlogN) 其实将时间复杂度为 O (logn) 的代码循环 N 遍的话，那么它的时间复杂度就是 n * O (logN)，也就是了 O (nlogN)。
「 空间复杂度 」
● 常数阶 O (1)
如果算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O (1)
空间复杂度 S (n) = O (1)
● 线性阶 O (n)
第 3 行新建一个数组出来，这个数据占用的大小随着 for 循环的增加而增加。所以
S (n) = O (n)
● 平方阶 O (n2)
二维数组，双层 for 循环生成。空间复杂度 S (n) = O (n2)
小憩一下
只有程序猿才看的懂的图
相关推荐
- 安全教育登录入口平台（安全教育登录入口平台官网）
-
122交通安全教育怎么登录:122交通网的注册方法是首先登录网址http://www.122.cn/，接着打开网页后，点击右上角的“个人登录”；其次进入邮箱注册，然后进入到注册页面，输入相关信息即可完...
- 大鱼吃小鱼经典版（大鱼吃小鱼经典版(经典版)官方版）
-
大鱼吃小鱼小鱼吃虾是于谦跟郭麒麟的《我的棒儿呢？》郭德纲说于思洋郭麒麟作诗的相声，最后郭麒麟做了一首，师傅躺在师母身上大鱼吃小鱼小鱼吃虾虾吃水水落石出师傅压师娘师娘压床床压地地动山摇。...
-
- 哪个软件可以免费pdf转ppt（免费的pdf转ppt软件哪个好）
-
要想将ppt免费转换为pdf的话，我们建议大家可以下一个那个wps，如果你是会员的话，可以注册为会员，这样的话，在wps里面的话，就可以免费将ppt呢转换为pdfpdf之后呢，我们就可以直接使用，不需要去直接不需要去另外保存，为什么格式转...
-
2026-02-04 09:03 off999
- 电信宽带测速官网入口（电信宽带测速官网入口app）
-
这个网站看看http://www.swok.cn/pcindex.jsp1.登录中国电信网上营业厅，宽带光纤，贴心服务，宽带测速2.下载第三方软件，如360等。进行在线测速进行宽带测速时，尽...
- 植物大战僵尸95版手机下载（植物大战僵尸95 版下载）
-
1可以在应用商店或者游戏平台上下载植物大战僵尸95版手机游戏。2下载教程：打开应用商店或者游戏平台，搜索“植物大战僵尸95版”，找到游戏后点击下载按钮，等待下载完成即可安装并开始游戏。3注意：确...
- 免费下载ppt成品的网站（ppt成品免费下载的网站有哪些）
-
1、Chuangkit（chuangkit.com）直达地址：chuangkit.com2、Woodo幻灯片（woodo.cn）直达链接：woodo.cn3、OfficePlus（officeplu...
- 2025世界杯赛程表（2025世界杯在哪个国家）
-
2022年卡塔尔世界杯赛程公布，全部比赛在卡塔尔境内8座球场举行，2022年，决赛阶段球队全部确定。揭幕战于当地时间11月20日19时进行，由东道主卡塔尔对阵厄瓜多尔，决赛于当地时间12月18日...
- 下载搜狐视频电视剧（搜狐电视剧下载安装）
-
搜狐视频APP下载好的视频想要导出到手机相册里方法如下1、打开手机搜狐视频软件，进入搜狐视频后我们点击右上角的“查找”，找到自已喜欢的视频。2、在“浏览器页面搜索”窗口中，输入要下载的视频的名称，然后...
- 永久免费听歌网站（丫丫音乐网）
-
可以到《我爱音乐网》《好听音乐网》《一听音乐网》《YYMP3音乐网》还可以到《九天音乐网》永久免费听歌软件有酷狗音乐和天猫精灵，以前要跳舞经常要下载舞曲，我从QQ上找不到舞曲下载就从酷狗音乐上找，大多...
- 音乐格式转换mp3软件（音乐格式转换器免费版）
-
有两种方法：方法一在手机上操作：1、进入手机中的文件管理。2、在其中选择“音乐”，将显示出手机中的全部音乐。3、点击“全选”，选中所有音乐文件。4、点击屏幕右下方的省略号图标，在弹出菜单中选择“...
- 电子书txt下载（免费的最全的小说阅读器）
-
1.Z-library里面收录了近千万本电子书籍，需求量大。2.苦瓜书盘没有广告，不需要账号注册，使用起来非常简单，直接搜索预览下载即可。3.鸠摩搜书整体风格简洁清晰，书籍资源丰富。4.亚马逊图书书籍...
- 最好免费观看高清电影（播放免费的最好看的电影）
-
在目前的网上选择中，IMDb（互联网电影数据库）被认为是最全的电影网站之一。这个网站提供了各种类型的电影和电视节目的海量信息，包括剧情介绍、演员表、评价、评论等。其还提供了有关电影制作背后的详细信息，...
- 孤单枪手2简体中文版（孤单枪手2简体中文版官方下载）
-
要将《孤胆枪手2》游戏的征兵秘籍切换为中文，您可以按照以下步骤进行操作：首先，打开游戏设置选项，通常可以在游戏主菜单或游戏内部找到。然后，寻找语言选项或界面选项，点击进入。在语言选项中，选择中文作为游...
欢迎 你 发表评论:
- 一周热门
-
-
抖音上好看的小姐姐，Python给你都下载了
-
全网最简单易懂!495页Python漫画教程，高清PDF版免费下载
-
飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx
-
win7系统还原步骤图解（win7还原电脑系统的步骤）
-
Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!
-
python入门到脱坑 输入与输出—str()函数
-
16949认证费用是多少（16949审核员太难考了）
-
linux软件（linux软件图标）
-
Python三目运算基础与进阶_python三目运算符判断三个变量
-
windows7旗舰版多少钱（win7旗舰版要多少钱）
-
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (77)
- python封装 (57)
- python写入txt (66)
- python读取文件夹下所有文件 (59)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)