目录Python全系列 教程
3567个小节阅读：5930.8k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
空间复杂度用于衡量算法占用内存空间随着数据量变大时的增长趋势。
这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”
算法在运行过程中使用的内存空间主要包括以下几种：
一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”
暂存空间可以进一步划分为三个部分。
暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。而空间复杂度更关注于数据的存储。指令空间的大小通常是固定的，与输入规模无关。
空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”
而空间复杂度只关注最差空间复杂度
常数级常见于数量与输入数据大小 $n$ 无关的常量、变量、对象。
注意
在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 $O(1)$
xxxxxxxxxxdef func(n:int): a = 0 b = 1 for i in range(n): a+=i b+=i print(a) print(b)xxxxxxxxxxdef func(n:int): a = 0 b = 1 for i in range(n): for i in range(n/2): a+=i b+=i print(a) print(b)线性级复杂度,常见于元素数量与 $n$ 成正比的数组、链表、栈、队列等：
xxxxxxxxxxdef func(n:int): arr = [0]*nxxxxxxxxxxdef func(n:int): print(n) if == 1: func(n-1)平方级复杂度,常见于矩阵和图，元素数量与 $n$ 成平方关系
xxxxxxxxxxdef func(n:int): arry = [[0]*n for i in range(n)] arry1 = [0]*n指数级复杂度随着输入数据规模的增加，运行空间呈爆炸性增长。常见于二叉树
xxxxxxxxxxdef func(n: int) -> int: if n == 0: return None root = Node(0) root.left = func(n-1) root.right = func(n-1) return root
与指数级相反，对数级反映了"每轮缩减到一半"的情况。设输入数据大小为 $n$ ，由于每轮缩减到一半
xxxxxxxxxxdef func(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1理想情况下，我们追求算法在时间和空间两方面都能取得最佳的性能。然而，实际上，提升时间复杂度通常需要牺牲空间复杂度，而反之亦然。这导致了一个经典的权衡：是选择“以空间换时间”还是“以时间换空间”。
在实际编码中，通常更重视时间效率，因此“以空间换时间”的策略更为常见。这意味着我们愿意使用更多的内存空间来提高算法的执行速度。当然，在处理大规模数据时，控制空间复杂度也变得至关重要。
实时效果反馈
1. 以下关于算法空间复杂度的说法错误的是?
A 常数级空间复杂度不随问题规模增大而改变
B 算法占用更少存储空间,空间复杂度也越低
C 算法中递归层数越深,空间复杂度一般越高
D 代码优化不会改变算法的空间复杂度
答案
1=>D