时间空间复杂度入门

labuladong原创

考虑到这是第一章，我不会对时空复杂度做面面俱到的讲解，详细的算法时空复杂度分析实用指南安排在你学完几种常见算法的核心框架之后，那时候你的知识储备可以轻松理解时空复杂度分析的各种场景。

因为本章后面的内容会带你实现常见的排序算法和数据结构，我会分析它们的时间复杂度，所以这里还是要提前介绍一下时间/空间复杂度的概念，以及分析时间/空间复杂度的简化方法，避免初学者疑惑。

对于初学者，你只需要记住以下几点：

1、时空复杂度用 Big O 表示法表示（类似 $O(1), O(n^2), O(logn)$ 等）。它们都是估计值，不需要精确计算，常数项和低增长项都可以忽略，仅需保留最高增长项。

比方说 $O(2n^2 + 3n + 1)$ 等同于 $O(n^2)$ ， $O(1000n + 1000)$ 等同于 $O(n)$ 。

2、我们分析算法复杂度时，分析的是最坏情况的复杂度。这一点会在下面的示例中体现。

3、时间复杂度用来衡量一个算法的执行效率，空间复杂度用来衡量算法的内存消耗，它们都是越小越好。

比方说时间复杂度 $O(n)$ 的算法比 $O(n^2)$ 的算法执行效率高，空间复杂度 $O(1)$ 的算法比 $O(n)$ 的算法内存消耗小。

当然，一般我们要说明这个 $n$ 代表什么，比如 $n$ 代表输入的数组的长度。

4、如何估算？现在你可以简单理解：时间复杂度大部分情况下就是看 for 循环的最大嵌套层数；空间复杂度就看算法申请了多少空间来存储数据。

注意

以上的分析方法中，有些细节并不严谨：

1、按照 for 循环的嵌套层数来估算时间复杂度是简化的方法，其实不完全准确。

2、大部分时候我们是分析最坏情况下的复杂度，但是对于数据结构 API 的复杂度衡量，我们会分析平均复杂度。

完善的复杂度分析方法会在算法时空复杂度分析实用指南具体介绍，以上估算方法对于学习本章内容足够了。

举几个例子来说比较直观。

时间/空间复杂度案例分析

示例一，时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ：

java

// 输入一个整数数组，返回所有元素的和 int getSum(int[] nums) {  int sum = 0;  for (int i = 0; i < nums.length; i++) {  sum += nums[i];  }  return sum; }

cpp

// 输入一个整数数组，返回所有元素的和 int getSum(vector<int>& nums) {  int sum = 0;  for (int i = 0; i < nums.size(); i++) {  sum += nums[i];  }  return sum; }

python

# 输入一个整数数组，返回所有元素的和 def getSum(nums: List[int]) -> int:  sum = 0  for i in range(len(nums)):  sum += nums[i]  return sum

// 输入一个整数数组，返回所有元素的和 func getSum(nums []int) int {  sum := 0  for i := 0; i < len(nums); i++ {  sum += nums[i]  }  return sum }

javascript

// 输入一个整数数组，返回所有元素的和 var getSum = function(nums) {  var sum = 0;  for (var i = 0; i < nums.length; i++) {  sum += nums[i];  }  return sum; }

算法包含一个 for 循环遍历 nums 数组，所以时间复杂度是 $O(n)$ ，其中 n 代表 nums 数组的长度。

我们的算法只使用了一个 sum 变量，这个 nums 是题目给的输入，不算在我们算法的空间复杂度里面，所以空间复杂度是 $O(1)$ 。

示例二，时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ ：

java

// 当 n 是 10 的倍数时，计算累加和，否则返回 -1 int sum(int n) {  if (n % 10 != 0) {  return -1;  }  int sum = 0;  for (int i = 0; i <= n; i++) {  sum += i;  }  return sum; }

cpp

// 当 n 是 10 的倍数时，计算累加和，否则返回 -1 int sum(int n) {  if (n % 10 != 0) {  return -1;  }  int sum = 0;  for (int i = 0; i <= n; i++) {  sum += i;  }  return sum; }

python

# 当 n 是 10 的倍数时，计算累加和，否则返回 -1 def sum(n: int) -> int:  if n % 10 != 0:  return -1  sum = 0  for i in range(n + 1):  sum += i  return sum

// 当 n 是 10 的倍数时，计算累加和，否则返回 -1 func sum(n int) int {  if n%10 != 0 {  return -1  }  sum := 0  for i := 0; i <= n; i++ {  sum += i  }  return sum }

javascript

// 当 n 是 10 的倍数时，计算累加和，否则返回 -1 var sum = function(n) {  if (n % 10 !== 0) {  return -1;  }  var sum = 0;  for (var i = 0; i <= n; i++) {  sum += i;  }  return sum; }

其实只有当 n 是 10 的倍数时，算法才会执行 for 循环，时间复杂度是 $O(n)$ 。其他情况下算法会直接返回，时间复杂度是 $O(1)$ 。

但是算法复杂度只考察最坏情况，所以这个算法的时间复杂度是 $O(n)$ ，空间复杂度是 $O(1)$ 。

示例三，时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ ：

java

// 数组是否存在两个数，它们的和为 target？ boolean hasTargetSum(int[] nums, int target) {  for (int i = 0; i < nums.length; i++) {  for (int j = i + 1; j < nums.length; j++) {  if (nums[i] + nums[j] == target) {  return true;  }  }  }  return false; }

cpp

// 数组是否存在两个数，它们的和为 target？ bool hasTargetSum(vector<int>& nums, int target) {  for (int i = 0; i < nums.size(); i++) {  for (int j = i + 1; j < nums.size(); j++) {  if (nums[i] + nums[j] == target) {  return true;  }  }  }  return false; }

python

# 数组是否存在两个数，它们的和为 target？ def hasTargetSum(nums: List[int], target: int) -> bool:  for i in range(len(nums)):  for j in range(i + 1, len(nums)):  if nums[i] + nums[j] == target:  return True  return False

// 数组是否存在两个数，它们的和为 target？ func hasTargetSum(nums []int, target int) bool {  for i := 0; i < len(nums); i++ {  for j := i + 1; j < len(nums); j++ {  if nums[i] + nums[j] == target {  return true  }  }  }  return false }

javascript

// 数组是否存在两个数，它们的和为 target？ var hasTargetSum = function(nums, target) {  for (var i = 0; i < nums.length; i++) {  for (var j = i + 1; j < nums.length; j++) {  if (nums[i] + nums[j] === target) {  return true;  }  }  }  return false; }

算法嵌套了两层 for 循环，所以时间复杂度是 $O(n^2)$ ，其中 $n$ 代表 nums 数组的长度。

我们的算法只使用了 i, j 两个变量，这是常数级别的空间消耗，所以空间复杂度是 $O(1)$ 。

你也许会说，内层的 for 循环并没有遍历整个数组，且有可能提前 return，算法实际执行的次数应该是小于 $n^2$ 的，时间复杂度还是 $O(n^2)$ 吗？

是的，还是 $O(n^2)$ 。具体到不同的输入，算法的实际执行次数确实会小于 $n^2$ ，但我们不需要关心这些细节，估算一个最坏情况的时间复杂度就可以了。

每层 for 循环在最坏情况下都是 $O(n)$ 的时间复杂度，套在一起，总的时间复杂度是 $O(n^2)$ 。

示例四，时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ：

java

void exampleFn(int n) {  int[] nums = new int[n]; }

cpp

void exampleFn(int n) {  vector<int> nums(n); }

python

def exampleFn(n: int):  nums = [0] * n

func exampleFn(n int) {  nums := make([]int, n) }

javascript

function exampleFn(n) {  let nums = new Array(n); }

这个函数中创建了一个大小为 n 的数组，所以空间复杂度是 $O(n)$ 。

上述代码申请数组空间并将 n 个元素初始化为 0。内存申请操作的时间复杂度可以认为是 $O(1)$ ，但为所有元素赋值的操作相当于一个隐藏的 for 循环（由编程语言为我们自动完成），时间复杂度是 $O(n)$ 。所以总的时间复杂度是 $O(n)$ 。

时间复杂度并不仅仅体现在你看得到的 for 循环，每一行代码都可能有隐藏的时间复杂度。所以说要了解编程语言提供的常用数据结构实现原理，这是准确分析时间复杂度的基础。

示例五，时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ：

java

// 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方 int[] squareArray(int[] nums) {  int[] res = new int[nums.length];  for (int i = 0; i < nums.length; i++) {  res[i] = nums[i] * nums[i];  }  return res; }

cpp

// 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方 vector<int> squareArray(vector<int>& nums) {  vector<int> res(nums.size());  for (int i = 0; i < nums.size(); i++) {  res[i] = nums[i] * nums[i];  }  return res; }

python

# 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方 def squareArray(nums: List[int]) -> List[int]:  res = [0] * len(nums)  for i in range(len(nums)):  res[i] = nums[i] * nums[i]  return res

// 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方 func squareArray(nums []int) []int {  res := make([]int, len(nums))  for i := 0; i < len(nums); i++ {  res[i] = nums[i] * nums[i]  }  return res }

javascript

// 输入一个整数数组，返回一个新的数组，新数组的每个元素是原数组对应元素的平方 var squareArray = function(nums) {  let res = new Array(nums.length);  for (let i = 0; i < nums.length; i++) {  res[i] = nums[i] * nums[i];  }  return res; }

算法初始化 res 数组需要 $O(n)$ 的时间复杂度，包含一个 for 循环，时间复杂度也是 $O(n)$ ，总的时间复杂度是还是 $O(n)$ 其中 n 代表 nums 数组的长度。

我们声明了一个新的数组 res，这个数组的长度和 nums 数组一样，所以空间复杂度是 $O(n)$ 。

好了，初学者明白上面这些基本的时间、空间复杂度分析暂时就够用了，继续往下学习吧。