数据结构 - 算法基础

---

---

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

从数据结构的角度来看，以下是算法的一些重要类别：

• 搜索 - 在数据结构中搜索项目的算法。

• 排序 - 按特定顺序对项目进行排序的算法。

• 插入 - 在数据结构中插入项目的算法。

• 更新 - 更新数据结构中现有项目的算法。

• 删除 - 从数据结构中删除现有项目的算法。

算法的特征

并非所有过程都可以称为算法。算法应具有以下特征：

• 明确性 - 算法应清晰明确。它的每个步骤（或阶段）及其输入/输出都应清晰，并且必须只有一个含义。

• 输入 - 算法应该有 0 个或多个明确定义的输入。

• 输出 - 算法应该有 1 个或多个明确定义的输出，并且应该与所需的输出相匹配。

• 有限性 - 算法必须在有限的步骤后终止。

• 可行性 - 应该使用可用资源可行。

• 独立性 - 算法应该有逐步的指示，这些指示应该独立于任何编程代码。

如何编写算法？

没有编写算法的明确标准。相反，它取决于问题和资源。算法从未编写为支持特定的编程代码。

众所周知，所有编程语言都共享基本的代码结构，例如循环（do、for、while）、流程控制（if-else）等。这些通用结构可用于编写算法。

我们以逐步的方式编写算法，但并非总是如此。算法编写是一个过程，并在问题域明确定义后执行。也就是说，我们应该知道我们正在为其设计解决方案的问题域。

示例

让我们尝试通过一个示例来学习算法编写。

问题 - 设计一个算法来添加两个数字并显示结果。

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

算法告诉程序员如何编写程序。或者，算法可以写成：

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

在算法的设计和分析中，通常使用第二种方法来描述算法。它使分析师能够轻松地分析算法，而忽略所有不需要的定义。他可以观察正在使用的操作以及流程是如何流动的。

编写步骤编号是可选的。

我们设计一个算法来获得给定问题的解决方案。一个问题可以用多种方式解决。

因此，可以为给定问题推导出许多解决方案算法。下一步是分析这些提出的解决方案算法并实施最合适的解决方案。

算法分析

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

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

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

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

算法复杂度

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

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

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

算法的复杂度f(n)根据n给出算法的运行时间和/或存储空间，作为输入数据的大小。

空间复杂度

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

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

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

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

Algorithm: 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) 随着输入规模的增加而线性增长。