算法中的时间复杂度和空间复杂度
一、背景
随着人工智能的纵深发展，我们会发现现在做算法很多时候都是通过掉包来解决问题了。Torch或者Tensorflow之类的深度学习库大大减少了算法工程师的工作量，而且在张量运算、反向传播等环节，这些深度学习库的模块设计也尽最大可能地降低了计算的时间和空间复杂度，从而不需要我们额外进行过多的干预。
如果不是科班读计算机相关专业的，相信不少朋友第一次听说时间复杂度和空间复杂度的概念是在找工作刷leetcode题的时候。但实际上在编程的过程中，时间复杂度和空间复杂度一直都是我们需要关注的内容。即便深度学习建模的过程不需要过多考虑，但在数据预处理、数据后处理等阶段，我们仍离不开对低时间复杂度和低空间复杂度代码的追求。同样一份数据，高效的数据处理程序有时候要比低效的程序效率高出数倍甚至上百倍，而这也是体现一个算法工程师专业能力的重要环节。
二、时间复杂度
时间复杂度是指算法执行所需的时间随输入规模的增长而增长的速率。它通常用大O符号（Big O notation）表示，描述了最坏情况下的时间增长趋势。时间复杂度帮助我们评估算法的效率，特别是在处理大规模数据时，一个时间复杂度低的算法通常比时间复杂度高的算法更快。一般来说，基本的时间复杂度类型包括以下几种（复杂度：O(1) < O(log n) < O(n) < O(n^2) < O(2^n)）：
1、常数时间复杂度 O(1)
算法的执行时间不随输入规模的变化而变化。例如访问数组中的某个元素，或者定义某个变量。一般来说只要不涉及循环的代码时间复杂度都是常数级的。
2、对数时间复杂度 O(log n)
算法的执行时间与输入规模的对数成正比。例如，当我们需要遍历一个有序数组并从中找到我们想要的数字对应的索引时，我们可以遍历这个数组逐个比对当前索引对应的元素是否是我们要找的，这时候的时间复杂度为O(n)，但如果我们使用二分查找则可以将时间复杂度缩短至O(log n)。一般来说，涉及二分法的程序都是对数时间复杂度，因为每次遍历都只对有效的那一半数据进行操作。
nums = [1, 3, 5, 6, 7, 8, 9, 10]
target = 6
# 遍历数组查找是线性的时间复杂度O(n)
for i in range(len(nums)):
if nums[i]==target:
print(i)
# 使用二分查找
def binary_search(nums, target):
left, right = 0, len(nums)
while left<=right:
mid = (left+right)//2
if nums[mid]>target:
right = mid-1
elif nums[mid]<target:
left = mid+1
else:
return mid
return left
index = binary_search(nums, target)
print(index)3、线性时间复杂度 O(n)
算法的执行时间与输入规模成正比。例如遍历一个长度为n的数组。下面的代码遍历了数组nums的每一个数字，那么它的时间复杂度就是线性的，最差时间复杂度为数组长度。一般来说，使用了一层for或者while循环的程序都是线性时间复杂度的。
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for num in nums:
print(num)4、平方时间复杂度 O(n^2)
算法的执行时间与输入规模的平方成正比。基本上两层for或者while就是平方时间复杂度了，三层循环就是O(n^3)，以此类推。
nums = [1, 2, 3, 4, 5, 10, 6, 7, 8, 9]
# 这里使用平方时间复杂度的两层循环找出有序列表中唯一乱序的位置
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[j]<nums[i]:
print(i)
break5、指数时间复杂度 O(2^n)
算法的执行时间随着输入规模的指数增长。例如，下面这个计算斐波那契数列的程序就是指数级别的时间复杂度，因为它会重复计算相同的子问题。
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# 测试
n = 10
print(f"Fibonacci({n}) = {fibonacci(n)}")对上面的这个代码，我们使用动态规划进行优化，就可以避免子问题的重复计算，从而将时间复杂度优化至O(n)。
def fibonacci_dp(n):
if n <= 0:
return 0
elif n == 1:
return 1
# 存储每一步的结果，后面的计算就不需要再重复
fib = [0] * (n + 1)
fib[1] = 1
for i in range(2, n + 1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
# 测试
n = 10
print(f"Fibonacci({n}) = {fibonacci_dp(n)}")三、空间复杂度
空间复杂度是指算法在执行过程中所需的内存空间随输入规模的增长而增长的速率。它也用大O符号表示。空间复杂度帮助我们评估算法的内存使用情况，特别是在内存资源有限的环境中。在开发过程中，了解空间复杂度可以帮助我们选择最合适的数据结构，以满足内存使用要求。常见复杂度如下（复杂度：O(1) < O(log n) < O(n) < O(n^2)）：
1、常数空间复杂度 O(1)
算法所需的空间不随输入规模的变化而变化。例如定义一个含有固定值的变量。
2、对数空间复杂度 O(log n)
算法所需的空间与输入规模的对数成正比。例如二分法等递归深度为log n的递归算法，其空间复杂度一般也是对数级别的。
3、线性空间复杂度 O(n)
算法所需的空间与输入规模成正比。例如，使用一个长度为n的数组存储数据，这时候的空间复杂度会随着数组规模的扩大而线性增长。
nums = []
for i in range(100):
nums.append(i)4、平方空间复杂度 O(n^2)
算法所需的空间与输入规模的平方成正比。例如，使用一个m x n的二维数组。
# 创建一个大小为10*10的矩阵
m = 10
n = 10
matrix = [[0]*n for _ in range(m)]四、总结
除了上面介绍的常见复杂度类型，还有各种组合的复杂度类型，例如O(m+n)、O(n*log n)等。这些是由于程序中使用了一些嵌套，从而导致复杂度的组合多种多样。例如在一个线性的for循环层中，对每一次的循环都使用一次二分查找，其时间复杂度就是O(n*log n)了。但是不论什么样的组合，都离不开上面的基础类别。
原文地址：https://blog.csdn.net/ChaneMo/article/details/145325998
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！