Python算法 00--时间复杂度和空间复杂度
off999 2024-10-07 12:16 22 浏览 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)
小憩一下
只有程序猿才看的懂的图
相关推荐
- python列表(List)必会的13个核心技巧(附实用方法)
-
列表（List）是Python入门的关键步骤，因为它是编程中最常用的数据结构之一。以下是高效掌握列表的核心技巧和实用方法：一、理解列表的本质可变有序集合：可随时修改内容，保持元素顺序混合类型：一个列表...
- Python列表(List)一文全掌握:核心知识点+20实战练习题
-
Python列表（List）知识点教程一、列表的定义与特性定义：列表是可变的有序集合，用方括号[]定义，元素用逗号分隔。list1=[1,"apple",3.14]lis...
- python编程中列表常见的9大问题，你知道吗?
-
Python列表常见错误及解决方案列表(list)是Python中最常用的数据结构之一，但在使用过程中经常会遇到各种问题。以下是Python列表使用中的常见错误及其解决方法：一、索引越界错误1.访问...
- python之列表操作（python列表操作函数大全）
-
常用函数函数名功能说明append将一个元素添加到列表中names=['tom']用法：names.append('tommy')注意事项：被添加的元素只会被添加到...
- 7 种在 Python 中反转列表的智能方法
-
1.使用reverse()方法（原地）my_list=[10,12,6,34,23]my_list.reverse()print(my_list)#output:[23,34,6,12,...
- Python教程-列表复制（python中列表copy的用法）
-
作为软件开发者，我们总是努力编写干净、简洁、高效的代码。Python列表是一种多功能的数据结构，它允许你存储一个项目的集合。在Python中，列表是可变的，这意味着你可以在创建一个列表后改变它的...
- 「Python程序设计」基本数据类型:列表(数组)
-
列表是python程序设计中的一个基本的，也是重要的数据结构。我们可以把列表数据结构，理解为其它编程语言中的数组。定义和创建列表列表中的数据元素的索引，和数组基本一致，第一个元素的索引，或者是下标为0...
- Python中获取列表最后一个元素的方法
-
技术背景在Python编程中，经常会遇到需要获取列表最后一个元素的场景。Python提供了多种方法来实现这一需求，不同的方法适用于不同的场景。实现步骤1.使用负索引-1这是最简单和最Pythoni...
- Python学不会来打我(11)列表list详解:用法、场景与类型转换
-
在Python编程中，列表（list）是最常用且功能最强大的数据结构之一。它是一个有序、可变、支持重复元素的集合，可以存储任意类型的对象，包括整数、字符串、布尔值、甚至其他列表。本文将从基础语法开始...
- 零起点Python机器学习快速入门-4-4-列表操作
-
Python列表的基本操作展开。首先，定义了两个列表zlst和vlst并将它们的内容打印出来。接着，使用切片操作从这两个列表中提取部分元素，分别得到s2、s3和s4三个新的列表，并打...
- python入门 到脱坑 基本数据类型—列表
-
以下是Python列表（List）的入门详解，包含基础操作、常用方法和实用技巧，适合初学者系统掌握：一、列表基础1.定义列表#空列表empty_list=[]#包含不同类型元素的列表...
- Python 列表(List)完全指南:数据操作的利器
-
在Python中，列表（list）是一种可变序列（mutablesequence），它允许我们存储和操作一组有序数据（ordereddata）。本教程将从基础定义（basicdefiniti...
- 如何快速掌握 Python中列表的使用
-
学习python知识，好掌握Python列表的使用。从概念上来讲，Python中的列表list是一种有序、可变的容器，可以存储任意类型的数据（包括其他列表）。以下是列表的常用的操作和知识：1....
- Python中的列表详解及示例（python中列表的用法）
-
艾瑞巴蒂干货来了，数据列表，骚话没有直接来吧列表(List)是Python中最基本、最常用的数据结构之一，它是一个有序的可变集合，可以包含任意类型的元素。列表的基本特性有序集合：元素按插入顺序存储可变...
- python数据类型之列表、字典、元组、集合及操作
-
Python数据类型进阶：列表、字典与集合在Python中，数据类型是编程的基础，熟练掌握常用数据结构是成为高级开发者的关键。上一篇文章我们学习到了Python的数据类型：字符串(string)、数...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python自定义函数 (53)
- python进度条 (67)
- python吧 (67)
- python字典遍历 (54)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python串口编程 (60)
- python读取文件夹下所有文件 (59)
- java调用python脚本 (56)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python人脸识别 (54)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)