Python算法 00--时间复杂度和空间复杂度
off999 2024-10-07 12:16 41 浏览 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)
小憩一下
只有程序猿才看的懂的图
相关推荐
- 安装win7系统usb无法识别（win7安装后 不认usb）
-
一、确认电脑是否有USB支持：1.右击“计算机”，选择“管理”；2.在左侧菜单栏中依次展开“设备管理器”→“系统设备”→“总线控制器”，可以看到有USB项；3.如果没有USB项，表示没有安装USB...
-
- 解除手机浏览器网页限制（手机怎么解除浏览器对网站的拦截）
-
如果要解除手机浏览器禁止访问网页，首先打开设置图标，进去打开屏幕使用时间选项，再打开内容和隐私访问限制选项，接着找到并打开允许的应用选项，然后找到Safari浏览器，把右侧的绿色开关打开，就解除禁止访问了。解决步骤：1.从手机中开启自带的浏...
-
2025-12-12 01:51 off999
- 如何彻底修复ie
-
可以通过清理缓存和数据来修复IE浏览器因为IE浏览器可能会受到缓存和数据的干扰，导致无法正常访问网页或者打开网页很慢。清理浏览器的缓存和数据可以解决这个问题，具体方法是：打开IE浏览器，点击“工具”-...
- 键盘强制关机键是什么（电脑键盘强制关机）
-
Ctrl+alt+delete一、按一下键盘上的win键，然后再按一下键盘上的右箭头(win7或者win8以上系统可能要按2下右箭头键)，这个时候就会弹出关机选择菜单，接下来只要回车就可以强制关机了...
- win10设置了不休眠仍休眠（win10电脑设置不休眠为什么还是会休眠）
-
win10设置了永不休眠还是休眠可能是设置错误导致的，解决方法如下1，打开任务计划程序，在操作里选择创建基本任务。2，第一步页面是让你写个你的任务名称，这个随意。3，点下一步后会来到触发器页面，在这里...
- 电脑底部任务栏卡死（电脑底部任务栏卡死是什么原因）
-
1、首先，先打开控制面板找到系统和安全点击进入：2、然后，在点击系统和安全中的系统进入：3、之后，在系统中靠左边的菜单中找到高级系统设置点击进入：4、然后在系统属性中找到性能并单击鼠标左键进入设置：5...
- 随身wifi怎么设置不让别人蹭网
-
1.设置更复杂的密码加密是防蹭网的主要途径，一定要在配置路由器的无线网络时，在“无线网络安全设置”选项中，开启WPA-PSK/WPA2-PSK加密功能，并设置较复杂的密码（数字字母符号的组合最好），而...
- 以太网驱动程序下载（以太网驱动下载 win7官网）
-
请更新以太网驱动！可以安装其原装的驱动程序！或用驱动之家或驱动精灵更新驱动！以太网的驱动名称是EthernetDriver。以太网驱动是计算机操作系统中的一个软件程序，用于控制和管理计算机与以太网之...
- 新主板怎么装系统（新主板装机设置教程）
-
我从网上搜的教程，试了下可以装，大家可以试一试可以使用u盘启动盘重装系统的方式来安装新系统，具体的步骤如下：1、先在一台能用的电脑上安装咔咔装机一键重装系统工具，插入一个8GB以上的空白U盘，...
- 为什么电脑突然少了dll文件（电脑缺失各种dll文件是什么原因）
-
DLL文件丢失通常是由以下原因引起的：病毒或恶意软件感染：病毒或恶意软件可能会删除系统中的一些DLL文件，导致程序无法正常工作。软件安装或卸载不当：在安装或卸载某些软件时，可能会误删系统中的一些DLL...
- win10去掉桌面图标小箭头（win10如何去掉桌面图标的小箭头）
-
1、首先开始图标右键找到运行或者按快捷键Win+R; 2、打开“运行”窗口后，输入“regedit”，确认会弹出注册表编辑器; &...
- 2014版本cad序列号及密码（2014年cad序列号）
-
序列号：356-72378422，密钥：001F1AutoCAD2014需要本地注册运行，别人无法帮你算出受人以鱼不如受人以渔要关闭杀毒软件和助手（切记：如果是Vista或windows7系统，请务必...
- gho文件浏览工具（打开gho文件）
-
利用GHO文件浏览工具即可在电脑上打开GHO文件，具体操作请参照以下步骤。1、打开浏览器搜索【GHO文件浏览工具】，打开链接下载好软件安装包，安装到电脑上。2、在电脑上打开软件之后，就会出现【Ghos...
- 三星 官网（三星 官网免费查询）
-
答：三星官网售后服务官网：http://support-cn.samsung.com/support/ServiceLocations.asp国家工信部电信设备进网管理网站查询移动设备真伪方式：方法一...
欢迎 你 发表评论:
- 一周热门
-
-
抖音上好看的小姐姐，Python给你都下载了
-
全网最简单易懂!495页Python漫画教程，高清PDF版免费下载
-
Python 3.14 的 UUIDv6/v7/v8 上新，别再用 uuid4 () 啦!
-
飞牛NAS部署TVGate Docker项目，实现内网一键转发、代理、jx
-
python入门到脱坑 输入与输出—str()函数
-
宝塔面板如何添加免费waf防火墙?（宝塔面板开启https）
-
Python三目运算基础与进阶_python三目运算符判断三个变量
-
(新版)Python 分布式爬虫与 JS 逆向进阶实战吾爱分享
-
失业程序员复习python笔记——条件与循环
-
使用 python-fire 快速构建 CLI_如何搭建python项目架构
-
- 最近发表
- 标签列表
-
- 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)