算法性能和特性-工具盒子

算法（Algorithm）这个单词最早出现在波斯数学家阿尔·花拉子密在公元 825 年的《印度数字算术》中。对算法普遍认可的定义是:

算法是对特定问题求解的步骤，在计算机中表现为指令的有序序列，是独立存在的一种解决问题的方法和思想。

对算法进行评估时，时间复杂度、空间复杂度和稳定性是用来描述算法性能和特性的重要概念。

算法的复杂度 {#title-0} ====================

算法复杂度是指算法在运行时所需要的资源，资源包括时间资源和内存资源。即：考虑算法性能时，主要考虑其：时间复杂度 、空间复杂度。

1.1 时间复杂度 {#title-1}

时间复杂度是用来描述算法在处理不同规模 的输入数据时所需的时间量。但是，一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。同时又由于算法会受到软硬件的影响很大：

硬件性能：不同计算机具有不同的硬件配置，包括处理器速度、内存容量、存储设备速度等。较强大的硬件通常可以更快地执行相同的算法。
操作系统：不同的操作系统可能对算法的执行有不同的影响。操作系统的调度策略、进程管理和资源分配可以影响算法的性能。
编程语言和编译器：使用不同的编程语言和编译器编写的算法可能会产生不同的机器代码，从而影响运行时间。一些编程语言提供更好的优化能力，可以生成更有效率的代码。

也使得我们无法给算法的复杂度给与合适的度量。但是，一个算法花费的时间与算法中语句执行的次数成正比例，即：哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为 T(n)。

// n + 1 个语句
int my_sum_a(int n)
{
	int sum = 0;

	for (int i = 0; i <= n; i++)
	{
		sum += i;
	}

	return sum;
}

// 2 个 语句
int my_sum_b(int n)
{
	int sum = 0;
	sum = (1 + n) * n / 2;

	return sum;
}

void test()
{
	int ret1 = my_sum_a(100);
	int ret2 = my_sum_b(100);
	printf("%d %d\n", ret1, ret2);
}

当 n = 1 时，两个算法执行的语句次数是一样的，但是当 n 等于 10 时，很明显 my_sum_a 的执行的语句次数更多。n 称为问题的规模，当 n 不断变化时，时间频度 T(n) 也会不断变化。当我们在评估一个算法的优劣时，考虑其在不同的输入规模下的变化规律更合适，这就是时间复杂度概念。

在进行算法分析时，语句的总执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随着 n 的变化并确定 T(n) 的数量级。

一般情况下，随着 n 增大，T(n) 增长最慢的算法称之为最优算法。

如何得到时间复杂度？

如何表示一个算法的时间复杂度？

用常数 1 取代运行时间中的所有的加法常数；
在修改后的运行次数中，只保留最高次项；
如果最高阶项存在且不是1，则去除与这个项相乘的常数。

分析1: 有 2 个算法 A 和 B，A 算法需要做 2n + 3 次操作，B 算法要做 3n + 1 次操作，谁更加快？

| 次数 | A(2n+3) | B(3n+1) | |---------|---------|---------| | n = 1 | 5 | 4 | | n = 2 | 7 | 7 | | n = 3 | 9 | 10 | | n = 10 | 23 | 31 | | n = 100 | 203 | 301 |

由表可知，当 n=3 时，A 算法比 B 越来越好。从中我们发现，随着 n 增大，后面无论是 +1 还是 +3 都不会影响算法最终的变化，所以我们可以忽略这些常数。

分析2:

算法 C： 4n + 8
算法 D： 2n^2^ + 1

| 次数 | C(4n+8) | D(2n^2^+1) | |----------|---------|------------| | n = 1 | 12 | 3 | | n = 2 | 16 | 9 | | n = 3 | 20 | 19 | | n = 10 | 48 | 201 | | n = 100 | 408 | 20001 | | n = 1000 | 4008 | 2000001 |

由表可知，当 n<=3 时，算法 C 效率要劣于算法 D，当 n>=3 时，算法 C 优于算法 D。
当去掉后面的常数结果并没有改变，甚至去掉与 n 相乘的常数，结果也不会发生变化，也就是说与最高次项相乘的常数并不重要。

分析3:

算法 E：2n^2^ + 3n + 1
算法 F：2n^3^ + 3n + 1

| 次数 | E(2n^2^+3n+1) | F(2n^3^+3n+1) | |---------|---------------|---------------| | n = 1 | 6 | 6 | | n = 2 | 15 | 23 | | n = 3 | 28 | 64 | | n = 10 | 231 | 2031 | | n = 100 | 20301 | 2000301 |

由表可知，当 n=1 时，两个算法结果相同，当 n>1 后，算法 E 效率优于算法 F。随着 n 增大，差异非常明显差异非常明显，最大次项指数大的，随着 n 增长，变化急剧增大。所以算法中的次要项也可以忽略，更加关注最高阶项的阶数。

| 执行次数函数 | 阶 | 非正式术语 | |------------------|----------|---------| | 12 | O(1) | 常数阶 | | 2n+3 | O(n) | 线性阶 | | 3n^2^+2n+1 | O(n^2^) | 平方阶 | | 5log~2~n+20 | O(logn) | 对数阶 | | 2n+3nlog~2~n+19 | O(nlogn) | nlog2n阶 | | 6n^3^+2n^2^+3n+4 | O(n^3^) | 立方阶 | | 2^n^ | O(2^n^) | 指数阶 |

常用时间复杂度所耗费的时间从小到大:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(2^n^)

O(n^3^)、O(2^n^) 除非是很小的值，哪怕 n 这是 100，都是噩梦般的运行时间，一般不去讨论它们。

1.2 空间复杂度 {#title-2}

空间复杂度（Space Complexity）是用来描述算法在执行过程中所需的内存空间的度量。它表示算法在处理不同规模的输入数据时，所需的额外内存空间随输入规模的增加而变化的情况。算法在运行过程中通常包括以下几个方面的内存开销：

固定空间开销：这包括算法所需的常量内存空间，不随输入规模而变化。例如，算法中的变量、常数大小的数据结构等。
动态空间开销：这部分包括随着输入规模的增加而动态分配或释放的内存空间，通常与数据结构的大小相关。例如，动态数组、链表、树等数据结构需要根据输入数据的大小分配内存。
递归调用的空间开销：递归算法的空间复杂度通常与递归调用的深度有关。每个递归调用都在栈上分配一些内存，因此递归算法的空间复杂度取决于递归深度。
输入数据本身的空间开销：如果算法需要复制或存储整个输入数据的副本，那么这部分内存开销也应该考虑在内。

空间复杂度度量的目标是确定算法在执行期间所需的最大额外内存空间。通常，较低的空间复杂度表示算法使用的内存更少，这对于具有有限内存资源的系统和嵌入式系统非常重要。虽然空间复杂度也是非常重要的评估算法的指标，但是我们更多情况下考虑的是时间复杂度。

空间换时间？

例如，假设有一个需要频繁读取大型数据集的应用程序。如果每次需要数据时都要从磁盘读取，那么这将耗费大量的时间。但是，如果应用程序在内存中维护一个缓存，将最近访问的数据存储在内存中，那么当需要数据时，它首先检查缓存，如果数据在缓存中，则直接返回，避免了磁盘读取。这样可以极大地减少读取数据的时间，从而提高了程序的性能。