【数据结构】时间、空间复杂度详解

大家有没有遇到过，为什么有些程序跑得飞快，而有些程序却慢得让人抓狂？我们可能都是这样认为的：他写的程序效率高等等，确实如此。但这背后隐藏着两个重要的概念：时间复杂度和空间复杂度。它们就像程序的“效率指标”，帮助我们评估程序的性能。

一、时间复杂度：衡量速度的尺子

简单来说，时间复杂度描述的是程序运行时间随输入规模变化的趋势。

假设，你今天要去图书馆看书，这个图书馆超级大，你开始寻找：

• 情况一： 你知道书名，直接在书架上找到它。无论书架上有多少本书，你只需要花费固定时间。这种情况下，时间复杂度是常数级别，记作 O(1)。例如，以下Java代码展示了访问数组第一个元素的操作，无论数组长度如何，其时间复杂度始终为O(1):

public int getFirstElement(int[] arr) {
  return arr[0]; 
}

对应函数图像：

• 情况二： 你只知道书的主题，需要逐本翻阅。如果书架上有10本书，你可能需要翻阅10次；如果书架上有100本书，你可能需要翻阅100次。在这种情况下，时间复杂度是线性级别，记作 O(n)，其中 n 代表书的数量。例如，以下代码展示了查找数组最大值的例子，需要遍历数组一次，时间复杂度为O(n):

public int findMax(int[] arr) {
  int max = arr[0];
  for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

对应函数图像：

• 情况三： 你需要将所有书按照作者排序，然后找到对应作者的书。排序需要比较和移动书，时间会随着书的数量增加而显著增长。这种情况下，时间复杂度可能为平方级别，记作 O(n^2)。例如，经典的冒泡排序算法就展现了 O(n^2) 的时间复杂度:

public void bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

除了上述例子，还有其他常见的时间复杂度级别：

• O(log n): 对数级别，时间复杂度随输入规模缓慢增长，例如二分查找算法：

public int binarySearch(int[] arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1; 
}

对应函数图像：

• O(n log n): 线性对数级别，常见于高效的排序算法，例如归并排序算法：

public void mergeSort(int[] arr) {
  if (arr.length <= 1) {
    return;
  }
  int mid = arr.length / 2;
  int[] left = Arrays.copyOfRange(arr, 0, mid);
  int[] right = Arrays.copyOfRange(arr, mid, arr.length);
  mergeSort(left);
  mergeSort(right);
  merge(arr, left, right);
}

private void merge(int[] arr, int[] left, int[] right) {
  int i = 0, j = 0, k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }
  while (i < left.length) {
    arr[k++] = left[i++];
  }
  while (j < right.length) {
    arr[k++] = right[j++];
  }
}

对应函数图像：

• O(2^n): 指数级别，时间复杂度随输入规模指数增长，非常耗时。例如，递归计算斐波那契数列的算法：

public int fibonacci(int n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

对应函数图像：

二、空间复杂度：衡量内存的消耗

空间复杂度描述的是程序运行过程中所需的内存空间随输入规模变化的趋势。

例如：

• 情况一： 你只需要存储数字的总和，只需要一个变量来存储这个值。这种情况下，空间复杂度是常数级别，记作 O(1)。 例如，以下代码计算两个数的和，只使用了常数个变量，空间复杂度为O(1):

public int sum(int a, int b) {
  return a + b; 
}

• 情况二： 你需要存储所有数字，需要一个数组来存放它们。如果数字的数量为 n，则空间复杂度是线性级别，记作 O(n)。例如，以下代码复制一个数组，需要创建一个和原数组大小相同的数组，空间复杂度为O(n):

public int[] copyArray(int[] arr) {
  int[] newArr = new int[arr.length];
  for (int i = 0; i < arr.length; i++) {
    newArr[i] = arr[i];
  }
  return newArr;
}

同样，空间复杂度也有对数级别 O(log n)，例如以下递归函数，每次递归调用都将问题规模缩小一半，栈空间的消耗呈对数增长：

public void recursiveFunction(int n) {
  if (n <= 1) {
    return;
  }
  recursiveFunction(n / 2); 
}

三、总结

时间复杂度和空间复杂度是评估程序性能的重要指标。

• 时间复杂度关注程序运行时间，空间复杂度关注程序内存消耗。

• 选择合适的算法，可以有效降低时间复杂度和空间复杂度，提高程序效率。犹如鱼与熊掌，二者不可兼得。

希望这篇文章能够帮助各位看官更好地理解时间复杂度和空间复杂度，让你在编写代码时更加得心应手！感谢各位看官的观看，下期见，谢谢~