本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
在计算机科学中,空间复杂度是算法运行所需的内存量与输入长度的函数关系。空间复杂度通常用渐近符号表示,例如 O(log n)、O(n)、O(n log n)、O(n^2) 或 O(2^n)。
算法的空间复杂度是运行算法所需的内存量与输入长度的函数关系。空间复杂度通常用渐近符号表示,例如 O(log n)、O(n)、O(n log n)、O(n^2) 或 O(2^n)。
要计算算法的空间复杂度,我们需要同时考虑算法使用的静态空间和动态空间。
静态空间是算法所需的空间量,与输入的大小无关。这包括程序代码和算法使用的任何静态数据结构所需的空间。
动态空间是随着输入大小的增加算法所需的空间量。这包括算法使用的任何动态数据结构所需的空间,例如堆栈、队列和树。
算法的总空间复杂度是静态空间和动态空间的总和。
下面是一些空间复杂度计算的例子。
如果运行算法所需的空间量与输入的大小无关,则称该算法具有恒定的空间复杂度。
具有恒定空间复杂度的算法的一个很好的例子是两个数字的相加。存储这两个数字所需的空间量与数字的大小无关。
如果运行算法所需的空间量与输入大小成对数关系,则称该算法具有对数空间复杂度。
具有对数空间复杂度的算法的一个很好的例子是二分查找。要执行二分搜索,我们需要将输入数组存储在内存中。但是,存储数组所需的空间量与输入大小成对数关系。
如果运行算法所需的空间量与输入的大小成正比,则称该算法具有线性空间复杂度。
具有线性空间复杂度的算法的一个很好的例子是线性搜索。要执行线性搜索,我们需要将输入数组存储在内存中。存储数组所需的空间量与输入的大小成正比。
如果运行算法所需的空间量为输入大小的 n log n,则称该算法具有 n log n 空间复杂度。
具有 n log n 空间复杂度的算法的一个很好的例子是合并排序。要执行合并排序,我们需要将输入数组存储在内存中。存储数组所需的空间量是输入大小的 n log n。
如果运行算法所需的空间量是输入大小的二次方,则称该算法具有二次空间复杂度。
具有二次空间复杂度的算法的一个很好的例子是冒泡排序。要执行冒泡排序,我们需要将输入数组存储在内存中。存储数组所需的空间量是输入大小的二次方。
如果运行算法所需的空间量是输入大小的指数,则称该算法具有指数空间复杂度。
具有指数空间复杂度的算法的一个很好的例子是蛮力搜索。要执行暴力搜索,我们需要将输入数组存储在内存中。存储数组所需的空间量是输入大小的指数。