时间复杂度和空间复杂度

Posted on Edited on In

时间复杂度和空间复杂度的概念

时间复杂度是指算法执行所需要的时间。通常情况下，我们用大 O 表示法来描述时间复杂度，其中 O(f(n)) 表示算法的最坏时间复杂度为 f(n)。

空间复杂度是指算法执行所需要的存储空间。通常情况下，我们也用大 O 表示法来描述空间复杂度，其中 O(f(n)) 表示算法的最坏空间复杂度为 f(n)。

在分析算法的时间和空间复杂度时，我们通常关注的是随着输入规模的增大，算法的执行时间和所需空间的变化情况。例如，如果算法的时间复杂度是 O(n^2)，则当输入规模增大时，算法的执行时间会呈平方级别增长。如果算法的空间复杂度是 O(n)，则当输入规模增大时，算法所需的存储空间也会呈线性增长。

计算时间复杂度

通常来说，计算算法的时间复杂度可以采用以下步骤：

  1. 分析算法的基本操作：首先要分析算法中执行的基本操作，并确定其时间复杂度。这通常是分析算法复杂度的第一步。

  2. 分析算法的执行次数：其次，要分析算法中基本操作的执行次数，即算法的时间复杂度的主要因素。

  3. 确定算法的时间复杂度：根据算法中基本操作的时间复杂度和执行次数，可以确定算法的时间复杂度。

例1

对于算法 A，如果分析出其中基本操作的时间复杂度为 O(1)，并且该基本操作会被执行 n 次，那么算法 A 的时间复杂度就是 O(n)。

例2：

假设我们有一个算法，该算法的流程如下：

从 1 到 n 遍历一个数组 A，执行基本操作 1
对于每个数字 x，从 1 到 x 遍历一个数组 B，执行基本操作 2
对于这个算法，我们可以分析其时间复杂度如下：

基本操作 1 的时间复杂度为 O(1)
基本操作 2 的时间复杂度为 O(1)
基本操作 1 在整个算法中会被执行 n 次，基本操作 2 在整个算法中会被执行 n(n+1)/2 次，因此算法的时间复杂度为 O(n+n(n+1)/2) = O(n^2)。

Master Theorem(又称为 Master 公式)

对于分治算法, 常常需要考虑三个方面：

  1. 划分子问题的代价：这可能包括复制数据的开销，或者对数据进行排序的开销。
  2. 解决子问题的代价：这可能包括递归调用的开销，以及在解决子问题时执行的其他操作的开销。
  3. 合并子问题的解决方案的代价：这可能包括对子问题的解决方案进行排序或合并的开销。
    如果某递归算法运行时间具有形式为递推关系的形式：
    T(n) = aT(n/b) + O(N^d)
    则其时间复杂度为下：
    condition 时间复杂度
    logba > d O(nlogba)
    logba < d nd
    logba = d O(nd * logn)

计算空间复杂度

我们可以通过以下方法来计算空间复杂度：

  1. 计算所使用的静态存储空间，即在程序运行之前就已经分配好的存储空间，包括常量、变量和数组等。
  2. 计算动态存储空间，即在程序运行过程中临时分配的存储空间，例如递归调用时使用的栈空间。

在计算空间复杂度时，应该将上述两种存储空间都考虑在内，最后使用大O表示法来表示结果。
分析所需空间大小时需要考虑以下几点：

  • 变量的数量：算法使用的变量数量与数据规模之间的关系。
  • 辅助数据结构的大小：辅助数据结构所使用的存储空间大小与数据规模之间的关系。
    一般来说，如果算法使用的存储空间大小与数据规模呈线性关系，空间复杂度为 O(n)；如果使用的存储空间大小是常数级别的，空间复杂度为 O(1)。
    举个例子，如果有一个算法使用了一个大小为 n 的数组来存储数据，那么它的空间复杂度就是 O(n)，因为数组的大小是与数据规模呈线性关系的。
    如果有一个算法只使用了几个常数个变量来存储数据，那么它的空间复杂度就是 O(1)，因为变量的数量是常数级别的。

例

用来求解一个数组中的最大子序列和。这个算法的时间复杂度是 O(n)（其中 n 是数组中元素的个数），空间复杂度是 O(1)，因为它只使用了常数个变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxSubsequenceSum(arr) {
  let maxSum = 0;
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (sum > maxSum) {
      maxSum = sum;
    } else if (sum < 0) {
      sum = 0;
    }
  }
  return maxSum;
}