Java 数据结构 - 算法分析

算法是一个逐步的过程，它定义了一组指令，这些指令以一定的顺序执行以获得所需的输出。算法通常是在底层语言之外创建的，即一个算法可以用多种编程语言实现。

算法分析

算法的效率可以在两个不同的阶段进行分析，即实现之前和实现之后。它们如下所示：

先验分析 − 这是对算法的理论分析。通过假设所有其他因素（例如处理器速度）都是恒定的并且对实现没有影响来衡量算法的效率。

后验分析 − 这是对算法的经验分析。使用编程语言实现所选算法。然后在目标计算机上执行此操作。在此分析中，将收集实际统计数据，例如运行时间和所需空间。

我们将学习先验算法分析。算法分析处理所涉及的各种操作的执行或运行时间。操作的运行时间可以定义为每个操作执行的计算机指令数。

算法复杂度

假设X是一个算法，n是输入数据的规模，算法X使用的時間和空間是决定X效率的两个主要因素。

时间因素 − 通过计算关键操作的数量（例如排序算法中的比较）来衡量时间。

空间因素 − 通过计算算法所需的最大内存空间来衡量空间。

算法f(n)的复杂度给出了算法的运行时间和/或存储空间，以n（作为输入数据的规模）表示。

空间复杂度

算法的空间复杂度表示算法在其生命周期中所需的内存空间量。算法所需的空间等于以下两个部分之和：

一个固定部分，即存储某些数据和变量所需的空间，这些数据和变量与问题的规模无关。例如，使用的简单变量和常量、程序大小等。

一个可变部分，即变量所需的空间，其大小取决于问题的规模。例如，动态内存分配、递归堆栈空间等。

任何算法P的空间复杂度S(P)为S(P) = C + SP(I)，其中C是固定部分，S(I)是算法的可变部分，它取决于实例特征I。以下是一个简单的例子，试图解释这个概念：

算法：SUM(A, B)

Step 1: START
Step 2: C <- A + B + 10
Step 3: Stop

这里我们有三个变量A、B和C以及一个常量。因此S(P) = 1 + 3。现在，空间取决于给定变量和常量类型的数据类型，并且将相应地进行乘法。

时间复杂度

算法的时间复杂度表示算法运行到完成所需的时间量。时间需求可以定义为数值函数T(n)，其中T(n)可以衡量为步骤数，前提是每个步骤消耗恒定时间。

例如，两个n位整数的加法需要n个步骤。因此，总计算时间为T(n) = c * n，其中c是两个位相加所需的时间。在这里，我们观察到T(n)随着输入规模的增加而线性增长。