当前位置:   article > 正文

空间复杂度

空间复杂度

什么是空间复杂度

空间复杂度是对一个算法在运行过程中占用内存空间大小的量度,记做S(n)=O(f(n))。

注意点:空间复杂度是考虑程序运行时占用内存的大小,而不是可执行文件(程序本身)的大小。空间复杂度只能预先大体评估程序内存使用的大小,而不是精确计算,因为很多因素会影响程序真正内存使用大小,例如编译器的内存对齐、编程语言容器的底层实现等等,这些都会影响到程序内存的开销。

举例说明

两个函数,空间复杂度分别为O(1), O(n)

  1. # O(1)
  2. def f1(n):
  3. j = 0
  4. for i in range(n):
  5. j += 1
  6. return j
  7. # O(n)
  8. def f2(n):
  9. a = []
  10. for i in range(n):
  11. a.append(i)
  12. return a
'
运行

在第一个函数中,所需开辟的内存空间并不会随着n的变化而变化,即此算法空间复杂度为一个常量,所以表示为O(1)。在第二个函数中,随着n的增大,开辟的内存大小呈线性增长,这样的算法空间复杂度为O(n)。在递归的时候,会出现空间复杂度为logn的情况,比较特殊。

斐波那契数列递归算法的性能分析

以斐波那契数列为例,做一下性能分析:

  1. def fibonacci(n):
  2. if n <= 0:
  3. return 0
  4. elif n == 1:
  5. return 1
  6. else:
  7. return fibonacci(n - 1) + fibonacci(n - 2)
'
运行

首先回顾一下时间复杂度:递归算法的时间复杂度 = 递归的次数 * 每次递归中的操作次数。每次递归进行了一次加法操作,时间复杂度是O(1),递归的次数可以抽象成一棵递归树:(以n=5为例)

 在这棵二叉树中每一个节点都是一次递归,一棵深度(按根节点深度为1)为k的二叉树最多可以有 2^k - 1 个节点,所以该递归算法的时间复杂度为O(2^n),这个复杂度是非常大的,随着n的增大,耗时是指数上升的。

然后再来看空间复杂度:递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

为什么要求递归的深度呢?因为每次递归所需的空间都被压到调用栈里(这是内存管理里面的数据结构,和算法里的栈原理是一样的),一次递归结束,这个栈就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

回到斐波那契数列的例子,每次递归所需要的空间大小都是一样的,所以每次递归中需要的空间是一个常量,并不会随着n的变化而变化,每次递归的空间复杂度就是 O(1)。递归的深度如图所示:

递归第n个斐波那契数的话,递归调用栈的深度就是n。那么每次递归的空间复杂度是O(1), 调用栈深度为n,所以这段递归代码的空间复杂度就是O(n)。

此算法时间复杂度非常高的主要原因是最后一行的两次递归,所以优化算法的方向就是减少递归的调用次数:

  1. def fibonacci(first, second, n): #初始值 first = second = 1
  2. if n <= 0:
  3. return 0
  4. elif n <= 2:
  5. return 1
  6. elif n == 3:
  7. return first + second
  8. else:
  9. return fibonacci(second, first + second, n - 1)
'
运行

举例来说 n=5 时 fibonacci(1,1,5) → fibonacci(1,2,4) → fibonacci(2,3,3) → 2+3=5。这里相当于用first和second来记录当前相加的两个数值,此时就不用两次递归了。因为每次递归的时候n减1,即只是递归了n次,所以时间复杂度是 O(n)。同理递归的深度是n-2,每次递归所需的空间还是常数,所以空间复杂度依然是O(n)。

最后总结一下:

可以看出,求斐波那契数的时候,使用递归算法并不一定在性能上是最优的,但递归确实简化了代码层面的复杂度。

二分法(递归实现)的性能分析

二分查找:

  1. def binary_search(arr, l, r, x):
  2. if r >= l:
  3. mid = l + (r - l) // 2
  4. if arr[mid] == x:
  5. return mid
  6. elif arr[mid] > x:
  7. return binary_search(arr, l, mid - 1, x)
  8. else:
  9. return binary_search(arr, mid + 1, r, x)
  10. else:
  11. return -1
'
运行

此算法时间复杂度为O(logn)。每次递归的空间复杂度主要就是参数里传入的这个arr数组,但需要注意的是在C/C++中函数传递数组参数,不是整个数组拷贝一份传入函数而是传入数组首元素地址。也就是说每一层递归都是公用一块数组地址空间的,所以每次递归的空间复杂度是常数即:O(1)。(Python呢?)再来看递归的深度,二分查找的递归深度是logn ,递归深度就是调用栈的长度,那么这段代码的空间复杂度为 1 * logn = O(logn)。

注意:关注语言在传递函数参数时,是拷贝整个数值还是拷贝地址,如果是拷贝整个数值那么该二分法的空间复杂度就是O(nlogn)。

学习自【代码随想录】

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/842071
推荐阅读
相关标签
  

闽ICP备14008679号