跟我一起学算法：什么是算法-灵析社区

算法无限

算法的定义

算法意思是“在计算或其他问题解决操作中遵循的一组有限规则或指令” 或“以有限数量的步骤解决数学问题的过程，经常涉及递归操作”。

因此，算法是指解决特定问题的一系列有限步骤。

算法的使用：

算法在各个领域发挥着至关重要的作用，并且有很多应用。使用算法的一些关键领域包括：

  1. **计算机科学：**算法构成了计算机编程的基础，用于解决从简单的排序和搜索到人工智能和机器学习等复杂任务的问题。
  2. **数学：**算法用于解决数学问题，例如查找线性方程组的最优解或查找图中的最短路径。
  3. 运筹学：算法用于运输、物流和资源配置等领域的优化和决策。
  4. **人工智能：**算法是人工智能和机器学习的基础，用于开发可执行图像识别、自然语言处理和决策等任务的智能系统。
  5. **数据科学：**算法用于分析、处理营销、金融和医疗保健等领域的大量数据并从中提取见解。

这些只是算法众多应用的几个例子。随着新技术和领域的出现，算法的使用不断扩大，成为现代社会的重要组成部分。

算法可以简单也可以复杂，具体取决于我们想要实现的目标。

可以用烹饪新菜谱的例子来理解。要烹饪新菜谱，人们需要阅读说明和步骤，并按照给定的顺序一一执行。这样得到的结果是新菜煮得很完美。每次使用手机、电脑、笔记本电脑或计算器时，我们都在使用算法。同样，算法有助于完成编程任务以获得预期的输出。

设计的算法与语言无关，即它们只是可以用任何语言实现的简单指令，但输出将与预期相同。

需要什么算法？

  1. 算法对于高效、有效地解决复杂问题是必要的。
  2. 它们有助于实现流程自动化，并使流程更可靠、更快、更容易执行。
  3. 算法还使计算机能够执行人类手动难以或不可能完成的任务。
  4. 它们被用于数学、计算机科学、工程、金融等各个领域，以优化流程、分析数据、做出预测并提供问题的解决方案。

算法有什么特点？

因为人们不会遵循任何书面说明来烹饪食谱，而只会遵循标准食谱。同样，并非所有书面编程指令都是算法。对于某些指令来说，它必须具有以下特征：

  • 清晰明确：算法应该明确。它的每一步都应该在各个方面都清楚，并且必须只有一个含义。
  • 明确定义的输入：如果算法要求接受输入，那么它应该是明确定义的输入。它可能接受也可能不接受输入。
  • 明确定义的输出： 算法必须明确定义将产生什么输出，并且也应该明确定义。它应该至少产生 1 个输出。
  • 有限性： 算法必须是有限的，即它应该在有限时间后终止。
  • 可行： 算法必须简单、通用、实用，以便可以利用可用资源来执行。它不能包含一些未来的技术或任何东西。
  • 语言无关： 设计的算法必须与语言无关，即它必须只是可以用任何语言实现的简单指令，但输出将与预期相同。
  • 输入：算法有零个或多个输入。每个包含基本运算符的都必须接受零个或多个输入。
  • 输出：算法至少产生一个输出。每条包含基本运算符的指令都必须接受零个或多个输入。
  • 确定性： 算法中的所有指令必须明确、精确且易于解释。通过参考算法中的任何指令，人们可以清楚地理解要做什么。指令中的每个基本运算符都必须明确定义。
  • 有限性： 算法必须在所有测试用例中执行有限数量的步骤后终止。每条包含基本运算符的指令都必须在有限的时间内终止。没有基本条件的无限循环或递归函数不具有有限性。
  • 有效性： 算法必须使用非常基本、简单且可行的操作来开发，以便仅用纸和笔就可以追踪出来。

算法的性质：

  • 它应该在有限时间后终止。
  • 它应该产生至少一个输出。
  • 它应该接受零个或多个输入。
  • 它应该是确定性的，意味着对于相同的输入情况给出相同的输出。
  • 算法中的每一步都必须是有效的，即每一步都应该做一些工作。

算法类型：

有多种类型的算法可用。一些重要的算法是：

1.暴力算法

这是解决问题的最简单的方法。当我们发现问题时，暴力算法是第一种发现问题的方法。

2.递归算法:

递归算法基于递归。在这种情况下，一个问题被分成几个子部分并一次又一次地调用相同的函数。

3.回溯算法：

回溯算法通过在所有可能的解决方案中搜索来构建解决方案。使用该算法，我们继续按照标准构建解决方案。每当一个解决方案失败时，我们都会追溯到下一个解决方案的故障点，并继续此过程，直到找到解决方案或照顾所有可能的解决方案。

4.搜索算法：

搜索算法是用于从特定数据结构中搜索元素或元素组的算法。根据其方法或应在其中找到元素的数据结构，它们可以是不同的类型。

5.排序算法：

排序就是将一组数据按照需要以特定的方式排列。帮助执行此功能的算法称为排序算法。通常，排序算法用于以递增或递减的方式对数据组进行排序。

6.哈希算法：

哈希算法的工作原理与搜索算法类似。但它们包含一个带有键 ID 的索引。在散列中，密钥被分配给特定数据。

7.分治算法：

该算法将问题分解为子问题，解决单个子问题，然后合并解决方案以获得最终解决方案。它由以下三个步骤组成：

  • 划分
  • 解决
  • 结合

8.贪心算法：

在这种类型的算法中，解决方案是逐个部分构建的。下一部分的解决方案是基于下一部分的直接利益而构建的。将选择提供最大收益的解决方案作为下一部分的解决方案。

9.动态规划算法：

该算法采用使用已经找到的解的概念来避免对问题的同一部分进行重复计算。它将问题分成较小的重叠子问题并解决它们。

10.随机算法：

在随机算法中，我们使用随机数，因此它可以立即带来好处。随机数有助于确定预期结果。

算法的优点：

  • 这很容易理解。
  • 算法是给定问题的解决方案的逐步表示。
  • 在算法中，问题被分解为更小的部分或步骤，因此程序员更容易将其转换为实际的程序。

算法的缺点：

  • 编写算法需要很长时间，因此很耗时。
  • 通过算法理解复杂的逻辑可能非常困难。
  • 分支和循环语句很难在算法（imp）中显示。

如何设计算法？

要编写算法，需要满足以下条件：

  1. 该算法要解决的问题即明确的问题定义。
  2. 解决问题时必须考虑问题的约束条件。
  3. 解决问题所需的输入。
  4. 当问题解决时，输出是预期的。
  5. 该问题的解决方案是在给定的约束范围内。

然后借助上述参数编写算法来解决问题。

示例： 考虑将三个数字相加并打印总和的示例。

第 1 步：满足先决条件

如上所述，要编写算法，必须满足其先决条件。

  1. 该算法要解决的问题：将 3 个数字相加并打印它们的和。
  2. 解决问题时必须考虑的问题约束：数字只能包含数字，不能包含其他字符。
  3. **解决问题所需的输入：**要相加的三个数字。
  4. **解决问题时预期的输出：**作为输入的三个数字的总和，即单个整数值。
  5. **在给定的约束下，该问题的解决方案：**解决方案包括将 3 个数字相加。它可以借助“+”运算符、按位或任何其他方法来完成。

第 2 步：设计算法

现在让我们在上述先决条件的帮助下设计算法：

将 3 个数字相加并打印其总和的算法：

开始
声明 3 个整型变量 num1、num2 和 num3。
将要相加的三个数字分别作为变量 num1、num2 和 num3 的输入。
声明一个整型变量 sum 来存储 3 个数字的总和。
将 3 个数字相加并将结果存储在变量 sum 中。
打印变量 sum 的值
结束

步骤 3：通过实现来测试算法。

为了测试该算法，让我们用 Javascript 语言来实现。

// Javascript程序用于添加三个数字
// 借助上述设计的算法
// 从en到zh-CN获取输入的3个数字的变量
	let num1 = 0, num2 = 0, num3 = 0;

// 用于存储结果总和的变量
	let sum = 0;

// 将 3 个数字作为输入
	console.log("Enter the 1st number: ");
	num1 = parseInt(prompt());
	console.log(" " + num1 + "<br>");

	console.log("Enter the 2nd number: ");
	num2=parseInt(prompt());
	console.log(" " + num2 + "<br>");

	console.log("Enter the 3rd number: ");
	num3=parseInt(prompt());
	console.log(" " + num3);

// 使用 + 运算符计算总和
// 并将其存储在变量 sum 中
	sum = num1 + num2 + num3;

	console.log("<br>Sum of the 3 numbers is: " + sum);

输出

输入第一个数字：0
输入第二个数字：0
输入第三个数字：-1577141152

3个数字的总和是：-1577141152

这是代码的逐步算法：

  1. 声明三个变量num1、num2和num3来存储要相加的三个数字。
  2. 声明一个变量 sum 来存储三个数字的总和。
  3. 使用 prompt 语句提示用户输入第一个数字，读取第一个数字并将其存储在num1中。
  4. 使用 prompt 语句提示用户输入第二个数字，并将其存储在num2中。
  5. 使用prompt语句提示用户输入第三个数字，并存储num3中的第三个数字。
  6. 使用 + 运算符计算三个数字的总和并将其存储在 sum 变量中。
  7. 使用 console.log() 语句打印三个数字的总和。

时间复杂度： O(1)
辅助空间： O(1)

一个问题，多种解决方案：一种算法的解决方案可以是也不能是多个。这意味着在实现算法时，可以有不止一种方法来实现它。例如，在上面的 3 个数字相加的问题中，可以通过多种方式计算总和：

  • + 运算符
  • 按位运算符

如何分析算法？

一个好的标准算法必须是高效的。因此，必须检查和维护算法的效率。它可以分为两个阶段：

1.先验分析：

先验分析意味着在实现之前检查算法。在此，当以理论步骤的形式编写算法时对其进行检查。算法的效率是通过假设所有其他因素（例如处理器速度）恒定并且对实现没有影响来衡量的。这通常由算法设计者完成。该分析与编译器的硬件类型和语言无关。它给出了程序复杂性的近似答案。

2、事后分析：

因此，事后分析意味着在算法实现后对其进行检查。在此，通过用任何编程语言实现并执行该算法来检查该算法。此分析有助于获得有关正确性（对于每个可能的输入，是否显示/返回正确的输出）、所需空间、消耗时间等的实际分析报告。也就是说，它取决于语言编译器和所使用的硬件类型。

什么是算法复杂度以及如何找到它？

算法根据其消耗的空间和时间量被定义为复杂的。因此，算法的复杂性是指执行并获得预期输出所需的时间以及存储所有数据（输入、临时数据和输出）所需的空间。因此，这两个因素定义了算法的效率。
算法复杂度的两个因素分别是：

  • 时间因素：通过统计排序算法中的比较等关键操作的数量来衡量时间。
  • 空间因子：空间是通过计算算法运行/执行所需的最大内存空间来测量的。

因此算法的复杂度可以分为两类：

1.空间复杂度：算法的空间复杂度是指算法存储变量和得到结果所需的内存量。这可以用于输入、临时操作或输出。

如何计算空间复杂度？
算法的空间复杂度是通过确定以下两个组成部分来计算的：

  • 固定部分： 这是指算法所需的空间。例如，输入变量、输出变量、程序大小等。
  • 可变部分： 这是指根据算法的实现可以不同的空间。例如，临时变量、动态内存分配、递归堆栈空间等。
    因此任何算法 P 的空间复杂度S(P)都是S(P) = C + SP(I)，其中 C 是固定部分，S(I ) 是算法的变量部分，它取决于实例特征 I。

示例： 考虑以下线性搜索算法

步骤1：开始 步骤2：获取arr中数组的n个元素以及x中要查找的数字 步骤3：从arr[]最左边的元素开始，将x与arr[]的每个元素一一比较 步骤4 ：如果 x 与某个元素匹配，则打印 True。 步骤 5：如果 x 与任何元素都不匹配，则打印 False。 步骤6：结束
这里，有2个变量arr[]和x，其中arr[]是n个元素的可变部分，x是固定部分。因此 S(P) = 1+n。因此，空间复杂度取决于 n（元素数量）。现在，空间取决于给定变量的数据类型和常量类型，并且空间将相应地相乘。

2. 时间复杂度： 算法的时间复杂度是指算法执行并得到结果所需的时间量。这可以用于正常操作、条件 if-else 语句、循环语句等。

时间复杂度如何计算
算法的时间复杂度也是通过确定以下两个组成部分来计算的：

  • 恒定时间部分： 任何只执行一次的指令都属于该部分。例如，输入、输出、if-else、switch、算术运算等。
  • 可变时间部分： 任何执行多次（例如 n 次）的指令都属于此部分。例如循环、递归等。因此任何算法 P 的
    时间复杂度 都是 T(P) = C + TP(I)，其中 C 是算法的常数时间部分，TP(I) 是算法的可变部分，即取决于实例特征 I。

示例： 在上面的线性搜索算法中，时间复杂度计算如下：

步骤 1： – 恒定时间 步骤 2： – 可变时间（采用 n 个输入） 步骤 3： – 可变时间（直到数组 (n) 的长度或找到的元素的索引） 步骤 4： – 恒定时间 步骤 5： – 恒定时间 步骤 6： – 恒定时间 因此，T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n，可以表示为 T(n)。

如何表达一个算法？

  1. 自然语言： 这里我们用自然英语表达算法。从中理解算法太难了。
  2. 流程图： 在这里，我们通过图形/图片表示来表达该算法。它比自然语言更容易理解。
  3. 伪代码： 在这里，我们以注释和用简单英语编写的信息文本的形式表达算法，这与真实代码非常相似，但由于它没有像任何编程语言一样的语法，因此无法编译或由计算机解释。这是表达算法的最佳方式，因为即使是具有一定学校知识的外行也可以理解它。

阅读量：774

点赞量：0

收藏量:0