大O：空间复杂度

在算法中，大 O 非常重要。我不知道是不是只有我一个人这样，但我感觉我花了更多时间去理解时间复杂度，而不是空间复杂度。随着应用程序规模的扩大，空间成为一个重要问题，这合情合理，但这通常是在考虑算法初始时间之后再考虑的。而且，人们总是说内存很便宜！

但空间复杂度仍然是大 O 符号的一个非常重要的部分，我认为它绝对值得一读，以便为下一次技术面试做好准备。

不过，我想强调的是，本文不会深入探讨空间复杂度的正式计算细节。我只是想在基础层面上重新讨论一下这个概念，以便于对算法进行简单的解释。

概述：什么是空间复杂度？

我认为GeeksforGeeks对此的解释非常清楚，但如果你不想点击该链接，以下是他们的定义：

算法的空间复杂度是指算法相对于输入大小所占用的总空间。空间复杂度包括辅助空间和输入所占用的空间。

他们继续讨论同样非常重要的辅助空间：

“辅助空间是算法使用的额外空间或临时空间。”

总而言之，空间复杂度指的是算法占用的总空间，而辅助空间指的是可以临时用于运行部分算法的空间。辅助空间会忽略初始数据结构的输入大小，并考虑函数内部的任何程序调用。

然后，他们给出了一个关于不同排序方法的空间复杂度的很好的例子：

归并排序使用 O(n) 辅助空间，插入排序和堆排序使用 O(1) 辅助空间。不过，所有这些排序算法的空间复杂度都是 O(n)。

如果您需要复习一下这些算法，您可以查看我的 Ruby 排序系列！

但是了解了这些排序算法后，我们可以推断插入排序和堆排序都是就地排序算法。这意味着它们只修改现有的数组，而该数组已经在空间上被考虑（输入），并且不需要额外的空间来完成。相比之下，归并排序不是一种就地排序算法，它要求每次将原始数组减半时都创建一个新数组。

因此，归并排序比插入排序或堆排序占用更多的辅助空间是有道理的，但最终这三种算法的总空间复杂度仍然是 O(n)。如果这还不清楚，以下这段引自《虚张声势者的空间复杂度指南》的话，确实让我更容易理解：

空间复杂度衡量的是算法所需的工作存储空间。这意味着在最坏的情况下，算法中任何一点需要多少内存。与时间复杂度一样，我们主要关注的是，随着输入问题的大小 N 的增长，空间需求（用大 O 表示）如何增长。

计算空间复杂度

当我们谈论大 O 时，我们知道时间和空间复杂度往往与 n 这个值有关。通常，n 表示给定数据结构中元素的数量，并可以确定执行函数所需的字节数。某些语言（例如 Java 和 C++）要求在向数据结构中添加任何内容之前，先分配声明该结构所需的空间！我只想简单说明一下，空间是以字节为单位计算的。本质上，n 既是元素的数量，也是执行函数所需的字节数。

考虑到这一点，我们可以将算法的内存消耗分解为三个不同的部分，它们主要影响空间复杂度：

变量和常量
- 任何纯粹基于固定且不随时间变化的变量或常量的函数或算法，其复杂度都为 O(1) 或常量空间。这些变量或常量始终占用相同的内存，因此程序运行结束后无需重新计算空间。
输入
- 函数启动时给出的初始参数对于空间复杂度至关重要。如果我们给定一个数组，那么我们已经知道需要为数组中的元素数量分配空间。
执行
- 有些函数会立即运行并完成，而有些函数可能是递归的，或者在其内部调用其他函数。这些函数可能会在自身完成时将其他函数保存在堆栈中等待执行。这两种情况的空间复杂度有所不同。如果一个函数在调用后立即完成，则不需要额外的空间来执行该函数。但是，对于递归函数或在其内部调用其他函数的函数，则需要额外的空间来保存等待执行的值。

示例

以下是一些关于如何计算空间复杂度的非常基本的示例：

1）

def get_sum(x, y, z)
  sum = 0
  sum = x + y + z
  return sum
end

对于此示例，我们可以看到只需要关注 3 个参数和 1 个变量。所有这些值都是固定的，将来不会改变。因此，总体空间复杂度为 O(1)。

2）

def get_sum(array)
  sum = 0
  for i in [0...array.length]
    sum += array[i]
  end
  return sum
end

在这个例子中，我们有一个 sum 变量，但也有一个 for 循环。任何循环都会占用与循环元素长度相同的空间。在这种情况下，我们需要循环遍历数组以找出数组中所有值的总和，因此我们的空间复杂度将是 O(n) 或线性的，其中 n 是数组中元素的数量。这是因为空间将以与 n 相同的速率持续增加。如果我们想象一个线性图，它就是一条对角线，值按比例增加，随着 n 的增大，所需的空间量也会增加。

3）

def get_sum(array)
  size = array.length
  if size == 1
    return array[0]
  else
    return (array[0] + get_sum(array[1...size]))
  end
end

我之所以想包含最后一个例子，是因为它引出了递归和空间复杂度的问题。我们可以看到，函数多次调用自身，你猜它的空间复杂度是多少？它实际上是 O(n)，因为每次函数再次调用自身时，都需要腾出空间来将值存储在堆栈中，等待执行。与迭代方法相比，这占用了更多的空间，因为迭代方法会反复使用相同的变量空间，因此空间复杂度只有 O(1)。

资源

如果没有其他人的深入讲解，我不可能写出这篇博文。以下是一些我发现确实有助于加深理解的文章和视频：

感谢您的阅读。一如既往，如果您有任何补充，请在下方留言。谢谢，祝您编程愉快！

文章来源：https://dev.to/mwong068/big-o-space-complexity-lcm