时间复杂度和空间复杂度

2024-11-09 16:30:57

一、时间复杂度简介

1、时间复杂度是什么

时间复杂度是计算机科学中的一个概念，用于描述算法的运行时间相对于输入大小的增长关系。它是衡量算法效率的重要指标之一。

2、时间复杂度的表示

时间复杂度通常使用大O符号（就是希腊字母 Omicron 的大写）表示，如 O(1), O(n), O(log⁡n)等。括号里面的是随着输入数据规模 n 的增大算法执行时间的增长率。

二、常数时间操作

由于某一个算法在不同的机器上面运行时的环境不同，实际运行时间也是不同的。所以时间复杂度不是直接测量某个算法在某个机器上的运行耗时，而是通过统计执行常数时间操作的次数。

所以，我们就要了解常数时间操作是什么。

1、常数时间操作是什么

常数时间操作是指不论输入大小如何，执行时间都保持不变的操作。这些操作包括基本的算术运算（加、减、乘、除）、变量赋值、数组访问等。

例如如下代码：

int a = 1;
int b = 1234567;
int c = a + b;
int d = a - b;
int e = a * b;
int f = a / b;

前面三个赋值操作，由于都是 int 类型，所以都是 32 位，所以在赋值时都要对 32 位进行赋值上对应的 0 或 1，所以说，不论赋值多大的数字，都要对 32 位进行赋值，所以时间是不变的。

对于后面的四则运算，在计算机底层中也是要对两个操作数的 32 位每一位进行操作的，所以说，无论操作数的值是多少，也都要对 32 位进行操作，时间也是固定的。

2、不同常数时间操作之间的差异

对于不同的常数时间操作之间，实际是有差异的，例如加法和乘法的耗时不同。

但是，在进行时间复杂度分析时，我们会忽略不同常数时间操作之间的耗时差异，例如忽略加法操作和乘法操作之间的耗时差异；同时也会忽略一次和多次常数时间操作之间的差异，例如：

int a = 0;// 将这一个赋值操作看为一个常数时间操作
int b = a + 1;// 将这里一个加法操作和一个赋值操作看为一个常数时间操作

这样忽略这些操作之间的差异，可以抵消相互之间的差异产生的影响，同时也可以让我们能更注重算法时间的增长率，而不是实际的算法时间。

三、时间复杂度的分析

1、分析方法

我们需要将算法的流程拆分到常数时间操作层面。

然后对常数时间操作进行计数，也就是计算进行了多少次常数时间的操作。

然后忽略低阶项和常数项，原因是它们对大规模输入的影响较小。比如，表达式的复杂度为，因为是主导项。

这种分析方法使得我们能更清晰地比较不同算法的性能。

2、不同数据状况下的表现

算法的时间复杂度通常考虑最差情况，这确保算法在任何情况下都有明确的性能保证。有时最佳和平均情况也可能被分析，具体情况取决于问题的性质和算法设计。

例如，快速排序的最差时间复杂度为，但平均时间复杂度是 $O(n\log n)$ ，在大多数情况下表现良好。

3、冒泡排序分析

    public static 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;
				}
			}
		}
	}

1）拆分到常数时间操作层面

对于中间的这一部分比较操作和赋值操作，我们将他们整体看为一个常数时间操作。然后进行分析。

2）对常数时间操作计数

这里我们假设数组的长度为 n，所以外层循环的次数就是 (n - 1) 次，内层循环的次数就是从 (n - 1)依次递减 1，最终减到到 1。

可以看到这是一个等差数列，我们对其进行求和，可以得到：

$(n - 1) + (n - 2) + ... + 1 = \frac{n(n - 1)}2$

也就是：

$\frac{n^2}2 - \frac n2$

3）忽略低阶项和常数项

可以得到最终结果为：

可以看到，实际上对于冒泡排序，它的时间复杂度是固定为的（如果忽略只比较和比较加赋值操作之间的耗时差异），无论怎样，它都会依次对两个数进行比较。

但是下面一个排序就不一样了：

4、插入排序分析

	public static void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int key = arr[i];
			int j = i - 1;

			while(j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = key;
		}
	}

首先我们分析最坏的情况，也就是数组恰好是逆序的（数组长度为 n）：

我们可以将比较操作和交换操作或者只有比较操作都看作为一样的常数时间操作。

由于数组是逆序的，所以每一次内层循环都要比较 i 次，i 是从 1 每次递增 1，一直递增到 (n - 1)，同样是一个等差数列，求和可得：

$1 + 2 + ... + (n - 1) = \frac{n(n - 1)}2$

忽略低阶项和常数项，结果为

然后我们分析最好的情况，也就是数组是已经排序好的（数组长度为 n）：

由于数组是排好序的，所以每次内层循环只要比较一次就会结束，所以总共会比较 (n - 1) 次，所以最终的结果为：

$\Omega (n)$

四、时间复杂度补充

1、时间复杂度类型

从性能好到性能差依次排序：

O(1)

O(log⁡n)

O(n)

O(nlog⁡n)

O(n2) ~ O(nk)

O(2n) ~ O(kn)

O(n!)

2、符号

大O符号通常用于表示算法的最坏情况时间复杂度。不过，也可以用于其他上下文。除了大O符号，还有：

Ω符号（大欧米伽）：表示算法的最好情况时间复杂度。

Θ符号（大西塔）：表示算法的平均情况或者准确的渐近复杂度，即算法在最好和最坏情况之间的界限。

可以看到我上面的最好的情况的时间复杂度是使用的Ω。更详细的可以查看参考资料。

五、空间复杂度

1、空间复杂度是什么

空间复杂度是一个算法的重要特性，用于描述算法执行过程中所需内存空间的量。它衡量的是算法在运行时使用的内存资源。

2、空间复杂度的表示

空间复杂度通常用大O符号表示，例如 O(n)O(n)、O(1)O(1) 等，其中 nn 是输入数据的大小。

3、空间复杂度的分析

计算空间复杂度时需要考虑：

输入数据结构的大小。
临时数据结构和变量的空间消耗。
递归调用时栈空间的使用。

六、额外空间复杂度

1、额外空间复杂度是什么

仅指算法执行过程中使用的额外空间，不包括输入数据本身所占用的空间。通常指算法所需的辅助空间，如递归栈、临时变量等。

关系：

总空间复杂度 = 输入空间 + 额外空间复杂度
额外空间复杂度是总空间复杂度的一部分，主要关注算法自身需要的额外内存。

2、额外空间复杂度分析示例

1）例子1

给函数传入一个数组，求出数组所有的元素之和。

这里我们就只需要在函数中在多创建一个变量，用来存储和，所以额外空间复杂度为：

2）例子2

给传入一个数组，将数组赋值到一个新数组中后并返回新数组。

这里的空间复杂度也是，因为这里的新数组的空间是问题中要求的，并不是我们为了解决这个问题所要开辟的空间。

参考资料：

复杂度简介 - OI Wiki (oi-wiki.org)

码农公寓