算法的需求

1. 为了理解问题的基本思想。

2. 为了找到解决问题的方法。

3. 为了提高现有技术的效率。

4. 为了理解设计算法的基本原则。

5. 为了比较算法相对于其他技术的性能。

6. 这是最好的描述方法，无需描述实现细节。

7. 算法向设计者清晰地描述了问题的需求和目标。

8. 好的设计可以产生好的解决方案。

9. 为了理解问题的流程。

10. 为了衡量方法在所有情况下的行为（或性能）（最佳情况、最坏情况、平均情况）

11. 借助算法，我们还可以识别算法所需的资源（内存、输入输出）周期。

12. 借助算法，我们将艺术转化为科学。

13. 为了理解设计原则。

14. 我们可以衡量和分析与输入大小相关的问题的复杂性（时间和空间），而无需实现和运行它；这将降低设计成本。

算法分析

分析是评估算法效率的过程。我们可以基于两个基本参数来分析算法

• 空间复杂度： 空间复杂度可以理解为算法运行完成所需的空间量。
• 时间复杂度： 时间复杂度是输入大小 n 的函数，指的是算法运行完成所需的时间量。

让我们用一个例子来理解它。

假设在计算机科学中有一个问题需要解决，一般来说，我们通过编写程序来解决问题。 如果你想用一些编程语言如 C 语言编写程序，那么在编写程序之前，有必要用一种非正式的语言编写一个蓝图。

换句话说，在实现代码之前，你应该用类似于英语的语言描述你想要包含在代码中的内容，以便它更具可读性和可理解性，这正是算法的概念。

一般来说，如果有一个问题 P1，那么它可能有许多解决方案，使得每个解决方案都被视为一种算法。 因此，可能存在许多算法，例如 A₁, A₂, A₃, …, A_n。

在你将任何算法实现为程序之前，最好找出这些算法中哪些在时间和内存方面更好。

最好在 时间 方面分析每种算法，这与哪种算法可以更快执行相关，以及与哪种算法占用更少内存的 内存 相关。

因此，算法的设计与分析讨论了如何设计各种算法以及如何分析它们。 在设计和分析之后，选择占用最少时间和最少内存的最佳算法，然后将其实现为 C 语言程序。

在本课程中，我们将更多地关注时间而不是空间，因为就硬件而言，时间实际上是一个更具限制性的参数。 拿一台电脑并改变它的速度并不容易。 因此，如果我们在特定平台上运行算法，那么或多或少会受到该平台在速度方面可以为我们提供的性能的限制。

然而，另一方面，内存相对来说更加灵活。 我们可以通过简单地添加存储卡来在需要时增加内存。 因此，我们将关注时间而不是空间。

运行时间是根据特定的硬件来衡量的，而不是一个可靠的衡量标准。 当我们在不同的计算机上运行相同的算法或使用不同的编程语言时，我们会遇到相同的算法需要不同的时间。

一般来说，我们进行三种类型的分析，如下所示

• 最坏情况时间复杂度： 对于 'n' 输入大小，最坏情况时间复杂度可以定义为算法完成其执行所需的最大时间量。 因此，它只不过是由在输入大小为 n 的实例上执行的最大步骤数定义的函数。
• 平均情况时间复杂度： 对于 'n' 输入大小，平均情况时间复杂度可以定义为算法完成其执行所需的平均时间量。 因此，它只不过是由在输入大小为 n 的实例上执行的平均步骤数定义的函数。
• 最佳情况时间复杂度： 对于 'n' 输入大小，最佳情况时间复杂度可以定义为算法完成其执行所需的最少时间量。 因此，它只不过是由在输入大小为 n 的实例上执行的最少步骤数定义的函数。