什么是算法？定义、特性和示例

算法是一组规则或一系列指令，必须按照这些规则或指令来执行，才能解决一个定义明确的问题。算法的正式定义是：它包含一组有限的指令，这些指令按特定顺序执行以完成特定任务。它不是完整的程序或代码；它只是问题的解决方案（逻辑），可以用流程图或伪代码以非正式描述的形式表示。

算法的特点

以下是算法的特性

• 定义明确的输入：算法具有一些输入值。我们可以向算法传递零个或多个输入值。
• 定义明确的输出：算法结束时，我们将获得一个或多个输出。
• 无歧义：算法应无歧义，这意味着算法中的指令应清晰简单。
• 有限性：算法应具有有限性。这里的有限性意味着算法应包含有限数量的指令，即指令应该是可计数的。
• 有效性：算法应有效，因为算法中的每条指令都会影响整个过程。
• 可行性：算法必须是实际的、简单的和通用的，以便能够用现有资源执行。它不得依赖于任何未来的技术或事物。
• 语言无关性：算法必须是语言无关的，这样算法中的指令就可以用任何语言实现并产生相同的输出。

算法的阶段

算法运行所涉及的典型阶段

• 问题：问题可以是现实世界中的问题，也可以是现实世界中问题的某个实例，我们需要为之创建程序或一组指令。这组指令称为算法。
• 算法：将为问题设计一个算法，该算法是一个循序渐进的过程。
• 输入：在设计完算法后，将所需的输入提供给算法。
• 处理和决策：处理单元根据算法处理提供的输入并产生所需的输出。
• 输出：输出是程序的结果。
• 终止：一旦所有步骤都成功执行并产生输出，算法就达到了其终止点。

为什么我们需要算法？

我们需要算法的原因如下：

• 这是必要的，因为它能有效、高效地解决复杂问题。
• 它为问题提供了一个定义明确的解决方案。
• 它有助于快速解决问题，并占用最少的资源（内存和时间）。
• 它可以在没有人为干预的情况下处理数据、执行操作和做出决策。
• 它被用于数学、计算机科学、工程、金融等各个领域，以优化流程。

现实世界中的算法示例

假设我们要制作柠檬汁。以下是制作柠檬汁所需的步骤：

步骤 1：首先，将柠檬切成两半。

步骤 2：尽量挤压柠檬，将汁液倒入容器中。

步骤 3：在其中加入两汤匙糖。

步骤 4：搅拌容器，直到糖溶解。

步骤 5：糖溶解后，加入一些水和冰。

步骤 6：将果汁放入冰箱冷藏 5 到 10 分钟。

步骤 7：现在，就可以饮用了。

上述现实世界中的例子可以直接与算法的定义进行比较。我们不能在步骤 2 之前执行步骤 3；我们需要按照特定顺序制作柠檬汁。算法也指出，为了执行特定任务，应按特定顺序遵循每条指令。

算法的属性

• 它应该在有限的时间内完成工作。
• 至少必须产生一个输出。
• 它应该接受零个或多个输入。
• 它应该是确定的，这意味着对于相同的输入，它将产生相同的输出。
• 算法的每一步都必须是有效的，这意味着每一步都应该完成一些工作。

算法的特征

以下是设计算法时需要考虑的因素：

• 模块化：如果给出了一个问题，并且我们可以将该问题分解为小的模块或小的步骤，这就是算法的基本定义，这意味着该特征已为算法完美设计。
• 正确性：算法的正确性定义为当给定输入产生所需输出时，这意味着算法已设计为算法。算法的分析已正确完成。
• 可维护性：这里的可维护性意味着算法的设计应该非常简单、结构化，以便在重新定义算法时，不会对算法进行重大更改。
• 功能性：它考虑了解决现实世界问题的各种逻辑步骤。
• 健壮性：健壮性意味着算法能够清楚地定义我们的问题。
• 用户友好性：如果算法不用户友好，那么设计者将无法向程序员解释它。
• 简洁性：如果算法简单，就容易理解。
• 可扩展性：如果任何其他算法设计者或程序员想使用您的算法，那么它应该是可扩展的。

算法的重要性

1. 理论重要性：当面对任何现实世界问题时，我们将其分解为更小的模块。要分解问题，我们必须理解所有理论方面。
2. 实践重要性：正如我们所知，理论离不开实践。因此，算法的重要性既可以被视为理论上的，也可以被视为实践上的。

算法问题

以下是在设计算法时出现的问题：

• 如何设计算法：正如我们所知，算法是一个循序渐进的过程，所以我们必须遵循一些步骤来设计算法。
• 如何分析算法效率：分析算法效率对于理解其性能至关重要，尤其是在输入大小不断增长的情况下。

算法方法

以下是在考虑算法的理论和实践重要性后用于设计算法的方法：

• 暴力算法：应用通用逻辑结构来设计算法。它也称为穷举搜索算法，该算法搜索所有可能性以提供所需的解决方案。这类算法有两种类型：
  1. 优化：找到问题的所有解决方案，然后选择最佳解决方案，或者如果已知最佳解决方案的值，那么当已知最佳解决方案时，它将终止。
  2. 牺牲：一旦找到最佳解决方案，它就会停止。
• 分治法：这是一种非常有效的算法实现。它允许您循序渐进地设计算法。它将算法分解为使用不同方法来解决问题。它使我们能够将问题分解为不同的方法，并为有效输入产生有效输出。此有效输出将传递给其他函数。
• 贪心算法：这是一种算法范例，它在每次迭代中都做出最优选择，以期获得最佳解决方案。它易于实现，并且执行速度更快。但很少有情况它能提供最优解决方案。
• 动态规划：它通过存储中间结果来提高算法的效率。它遵循五个不同的步骤来找到问题的最优解决方案：
  • 它将问题分解为子问题以找到最优解决方案。
  • 在分解问题之后，它从这些子问题中找到最优解决方案。
  • 存储子问题的结果称为记忆化。
  • 重用结果，以便不为相同的子问题重新计算。
  • 最后，它计算复杂程序的最终结果。
• 分支定界算法：分支定界算法只能应用于整数规划问题。这种方法将所有可行解集划分为更小的子集。然后评估这些子集以找到最佳解决方案。
• 随机化算法：正如我们在常规算法中所见，我们有预定义的输入和所需的输出。那些具有一组定义的输入和所需输出并遵循一些描述步骤的算法称为确定性算法。当随机变量引入随机化算法中时会发生什么？在随机化算法中，算法引入了一些随机位并将其添加到输入以产生随机性质的输出。随机化算法比确定性算法更简单、更高效。
• 回溯法：回溯法是一种算法技术，它递归地解决问题，并在不满足问题约束时删除解决方案。

算法类别

算法的主要类别如下：

• 排序：为按特定顺序对项目进行排序而开发的算法。
• 搜索：为在数据结构中搜索项目而开发的算法。
• 删除：为从数据结构中删除现有元素而开发的算法。
• 插入：为将项目插入数据结构而开发的算法。
• 更新：为更新数据结构中现有元素而开发的算法。

算法分析

比较算法的时间和空间复杂度增长率的过程。算法可以在两个级别上进行分析，即第一个级别是在创建算法之前，第二个级别是在创建算法之后。以下是算法的两种分析：

• 先验分析：在这里，先验分析是算法的理论分析，是在实现算法之前完成的。在实现算法之前可以考虑各种因素，例如处理器速度，这不会影响实现部分。
• 后验分析：在这里，后验分析是算法的实际分析。通过使用任何编程语言实现算法来获得实际分析。此分析基本上评估算法占用的运行时间和空间。

以下是先验分析和后验分析之间的区别。

算法复杂度

算法的性能可以由两个因素衡量：

时间复杂度

算法的时间复杂度是指完成其执行所需的时间量。大 O 符号表示算法的时间复杂度。这里，大 O 符号是表示时间复杂度的渐近符号。时间复杂度主要是通过计算完成执行的步骤数来计算的。让我们通过一个例子来理解时间复杂度。

在上面的代码中，循环语句的时间复杂度至少为 n，如果 n 的值增加，则时间复杂度也会增加。而代码的复杂度，即 return sum，将是恒定的，因为它不依赖于 n 的值，并且将在一步内提供结果。我们通常考虑最坏情况复杂度，因为这是给定输入大小的最大时间。

空间复杂度

算法的空间复杂度是指解决问题并产生输出所需的空间量。与时间复杂度类似，空间复杂度也用大 O 符号表示。

对于算法，空间是为以下目的而需要的：

1. 存储程序指令
2. 存储常量
3. 存储变量
4. 跟踪函数调用、跳转语句等。

辅助空间

算法所需的额外空间（不包括输入大小）称为辅助空间。空间复杂度同时考虑了辅助空间和输入所使用的空间。因此，我们可以使用以下公式计算空间复杂度：

算法类型

以下是算法的类型：

• 搜索算法
• 排序算法

搜索算法

在计算机中，存储了大量数据，每当用户请求任何数据时，计算机就会在内存中搜索该数据并将其提供给用户。在数组中搜索数据的技术主要有两种：

• 线性搜索
• 二分搜索

线性搜索

线性搜索是一种非常简单的算法，它从数组的开头开始搜索元素或值，直到找到所需元素为止。它将要搜索的元素与数组中的所有元素进行比较；如果找到匹配项，则返回元素的索引，否则返回 -1。此算法可以在未排序的列表上实现。

二分搜索

二分算法是最简单的算法，可以非常快速地搜索元素。它用于在排序列表中搜索元素。要实现二分算法，元素必须按顺序存储或以排序方式存储。如果元素存储是随机的，则不能实现二分搜索。它用于查找列表的中间元素。

排序算法

排序算法用于按升序或降序重新排列数组或给定数据结构中的元素。比较运算符决定了元素的顺序。

为什么我们需要排序算法？

1. 需要高效的排序算法来优化其他算法的效率，例如二分搜索算法，因为二分搜索算法需要一个按特定顺序排序的数组，主要是按升序。
2. 它以人类可读的排序格式生成信息。
3. 在排序列表中搜索特定元素比在未排序列表中搜索要快。

如何表示算法？

• 自然语言：算法用自然英语表示。从中理解算法过于困难。
• 流程图：算法通过对其进行图形/图示表示来表达。与自然语言相比，它更容易理解。
• 伪代码：算法以信息丰富和注释的文本形式表示，用普通英语编写，类似于实际代码，但它没有像任何编程语言那样的语法。

它不能被计算机解释或编译。它是表达算法的最佳方式。这是因为即使是具有一些学校知识的普通人也能理解它。

示例

让我们举一个相加两个数字的例子。我们将用自然语言、流程图和伪代码来表达其算法。

自然语言

简单来说，相加两个数字遵循一个直接的过程：

1. 向用户询问第一个数字（a）。
2. 向用户询问第二个数字（b）。
3. 通过将两个数字相加（a+b）来执行加法。
4. 向用户显示结果（总和）。

流程图

伪代码

算法的优点

• 易于理解。
• 算法提供了解决给定问题的分步表示，使其易于理解。
• 在算法中，问题被分解为更小的步骤或组件。因此，程序员根据算法编写实际程序变得更加容易。

算法的缺点

• 编写算法可能是一个耗时的过程。由于编写算法需要很长时间，所以确实很耗时。
• 借助算法理解复杂逻辑并不容易。
• 在算法中显示循环和分支语句很困难。

算法选择题

1. 用于执行计算或某些其他问题解决方法的一组规则或过程称为____________。

1. 数据结构
2. 程序
3. 算法
4. 计算

2. 算法的主要类别是

1. 搜索
2. Sort
3. 插入
4. 以上全部

3. 哪种算法用于按升序或降序排列元素？

1. 线性搜索算法
2. 二分查找算法
3. 排序算法
4. 无

4. 下列哪一项不是算法的属性？

1. 它在有限时间内完成工作。
2. 它不应该是确定的。
3. 它应该接受零个或多个输入。
4. 它应该产生至少一个输出。

5. 下列哪一项/哪些是算法的特征？

1. 无歧义
2. 有效性
3. 有限性
4. 以上全部