1、前文

能量巨大的算法

本文将简要概述算法、算法在计算中的作用以及计算机科学中主要使用的算法的概述。

从定义术语“算法”开始。

2、什么是算法

• 算法是解决特定问题或完成特定任务的分步过程。
• 如果一个算法对于每个输入都给出正确/预期的输出，则该算法被认为是正确的。
• 如果算法对某些输入给出了正确的输出，而对某些其他输入给出了错误的输出，那么该算法是不正确的。
• 我们可以用简单的语句表示算法，如句子、计算机程序或流程图。
• 每当我们讨论计算机科学中的算法时，它都包含两个方面：设计算法 + 分析算法

算法构成

3、程序与算法的区别

程序也是解决计算问题的分步过程。但是，算法和程序之间是有区别的。

程序 VS 算法

4、算法特点

确定性

每条指令都清晰明确。每一步都应该只有一个含义，即没有歧义。

输入

零个或多个明确定义的输入。

输出

至少生成一个输出。输出必须与预期/所需输出相同。

有限性

在任何情况下，算法都会在有限步骤数后终止。

与语言无关

算法从来都不是特定于语言的。我们可以用我们选择的任何编程语言实现该算法。

有效性

每条指令都是非常基本的，因此可以通过计算来执行。这也总是可行的

5、算法数据流

问题

我们首先明确定义问题，为其设计一个有效的算法。

算法

它是旨在解决上述问题的指令集。

输入

一旦我们设计了算法，我们就向它输入所需的值来实现。

处理单元

输入进入处理单元，然后由处理单元计算问题并产生所需的输出。

输出

这是算法的最终结果。只有当最终结果与预期结果相同时，该算法才能正确实现。

6、为什么需要算法

graph of Data Structure

可扩展性

假设有一个很大的现实世界问题。为了解决这样的问题，首先需要将其分解为更小的步骤，即缩小问题以获得更好的分析和效率。

性能

需要确保想要的问题解决方案是否可行。设计算法有助于实现这一目标。

7、影响算法的因素

影响算法的因素

在设计算法时，我们需要注意某些因素，例如：

模块化

模块化意味着将问题分解为更小的子问题/模块。精心设计的算法始终是模块化的。

正确性

如果对于给定的输入，实际输出和期望输出完全相同，则算法是正确的。

可维护性

这意味着以一种易于理解的方式构建算法。可维护性还包括能够轻松重新定义算法。

功能

功能定义了算法用于解决计算问题的各种逻辑步骤。

用户友好性

如果设计人员能够轻松地向程序员解释算法，那么算法是用户友好的。

稳健性

鲁棒性定义了算法可以定义或解决问题的清晰度。

可扩展性

如果任何其他设计人员也可以轻松使用它，则算法是可扩展的。

简单性

算法应该简单易懂。

8、算法的重要性

算法从两个方面很重要：

理论

如果我们不能从理论上理解一个算法，那么就很难实现它。从理论理解方面将问题划分为更小的子问题非常重要。

实用性

没有实施，理论就什么都不是。因此，一旦我们实施了问题，我们实际上就能够解决问题。

9、算法分析

算法分析流程

因此，算法的效率在两个不同的阶段进行分析：

• 实施前（事前分析）
• 实施后（后验分析）

前期分析

此分析是在设计算法后立即完成的。先验分析是一种理论分析，我们通过假设处理器速度等因素不影响效率来衡量算法的效率。

后验分析

它是对实现算法的实际分析。它考虑了所有因素，例如处理器速度、实现它的语言、所涉及的硬件等。

为什么要分析？

算法分析

• 对于单个问题，可能有多种类型的解决方案，即一个问题可以有多种算法来解决问题。
• 例如，如果我们想对给定的数字序列进行排序，我们可以使用排序算法来做到这一点。
• 有多种排序类型。事实上，总共有近 150 种分类类型。
• 在这种情况下，我们需要根据内存内部占用的计算时间和空间来决定哪种算法或逻辑最适合解决我们的问题。
• 这就是算法分析的用武之地。

10、针对算法存在的问题

通过算法分析来决定两个因素。这些因素是：

1. 我们什么时候可以比其他算法更好地调用算法来找到同一问题的解决方案？

2. 检查哪种算法性能更好的决策/测量标准是什么？

一种算法将优于其他算法，具体取决于检查任何算法效率的各种测量标准。

11、算法效率的衡量标准

有两个标准用于测量/分析任何算法的效率。这些标准是：

1. 算法的运行时间

2. 算法占用的空间/内存

在这里，我们谈论的是衡量算法的效率，而不是程序。

算法运行时间

算法的运行时间是指算法完全执行所需的时间。但是，算法只是程序的抽象表示。这不是实际的实现。那么，我们如何才能找到一个算法的运行时间呢？

时间复杂度

一种方法是将算法实际实现到程序中，并查看该程序执行所需的时间。这就是“实验方法”。然而，该实验方法有许多局限性，例如：

• 很难坐下来衡量一个程序需要多少时间才能执行。
• 不知道输入值的范围，这就是为什么我们需要手动检查各种输入，每次都使用不同的输入运行程序很多次。这一切都很麻烦。
• 每当编程语言出现时，它都会对机器产生依赖性。因此，根据计算机的硬件和操作系统，同一组代码在两台不同计算机上的运行时间可能会有所不同。
• 如果在 C 和 Python 中实现相同的算法，运行时间将再次变化。在运行时间方面，C 比 Python 快得多。这是因为 Python 中存在庞大的模块。因此，我们将在不同的编程语言中获得不同的运行时间。
• 所有这些因素都得出结论，实验分析不是衡量任何算法效率的好方法。
• 想要一种独立于机器、硬件、软件、编程语言的通用方法，并且能够处理所有可能的输入大小。
• 通常，运行时间将始终取决于输入大小。因此，输入大小的增加总是会增加运行时间。这是我们运行时间分析的基础。
• 在整个算法分析中，从不测量任何算法的准确运行时间，而是进行近似值。将其描述为渐近分析。

空间/内存

内存条

这是分析任何算法的另一个参数。

任何算法的空间复杂度都是算法占用的空间/内存总量，与输入大小有关。

通过一个例子来理解空间复杂性的概念。在这里，将尝试使用两种不同的方法计算数字的幂：

• 使用迭代方法
• 使用递归方法

然后检查他们的空间复杂性。

迭代方法

这里只使用四个自动变量。因此，该程序占用的空间是恒定的。

int pow_iterative(int base, int exponent){    for(i=0; i<exponent; i++)        power = power*base;}

递归方法

每当递归出现时，堆栈也会随之而来，因为递归使用堆栈来实现。

在执行递归时，一次又一次地调用该函数，这会增加程序使用的内存。

int pow_recursive(int base, int exponent){    if(exponent == 1)        return base;    return base * pow_recursive(base, exponent-1);}

由于堆栈在递归中的使用，该程序具有阶数“n”的空间复杂度，即线性阶数高于常数阶。

因此，可以在这里得出结论，就空间复杂性而言，寻找数字幂的迭代方法比计算相同问题的递归方法更好、更有效。

12、算法复杂性

到目前为止，算法的性能是由两个因素来衡量的——运行时间、使用的内存。基于这两个因素，算法具有以下两种形式的复杂性：

时间复杂度

时间复杂度定义为算法完成其所花费的时间。为了计算时间复杂度，我们计算算法执行所需的步骤数。

空间复杂度

它是进程在执行时获取的总内存。

13、算法设计

• 设计任何算法的方法和方法都有很多种。
• 在设计算法时，必须牢记该算法的运行时间和算法将使用的内存。
• 因此，在算法设计过程中，从所有可能的方法中利用该方法，这在效率方面提供了最佳结果。
• 在为特定问题设计算法时，试图最大限度地降低算法的时间和空间复杂性。

14、算法策略设计

有许多标准方法可以基于不同的策略设计算法。

蛮力技术

这是设计算法的一般和最简单的方法。它只是涉及一个直接的基于逻辑的结构来设计算法。这也称为“穷举搜索算法”。

分而治之的方法

大问题化解为小问题

这种方法基于将问题划分为更小的子问题并解决这些子问题。一旦子问题得到解决，我们就会将这些子问题的解决方案结合起来，得到最终的解决方案。

贪心算法

贪心算法

该算法在每次迭代中做出最佳选择，以获得最佳解决方案。

动态规划

它存储中间结果以提高算法的效率。它是一种基于递归的优化算法。在动态规划中，我们也存储子问题的结果，这样我们甚至不需要重新计算这些子问题。

随机算法

顾名思义，该算法利用随机数来决定算法的下一步。它的逻辑涉及一定程度的随机性。与其他标准算法相比，这种随机性是为了降低算法的复杂性。

回溯

它还以递归方式解决问题。它涉及搜索解决计算问题的所有可能组合，并删除那些不满足问题约束的子解决方案。

分支和绑定

它是一种用于解决组合、离散和一般数学问题的优化算法。它涉及划分问题，为它们获取子解决方案，然后找到最佳解决方案。

用于设计不同算法的技术也称为算法设计模式。设计算法的技术在计算过程中起着非常重要的作用，因为它将决定算法占用的计算时间和内存。

15、算法类别

搜索 ：用于在数据结构中搜索特定项的算法。

排序 ：按特定顺序对元素进行排序的算法。

删除 ：用于从数据结构中删除特定元素的算法。

插入 ：在数据结构中插入特定项的算法。

更新 ：用于更新数据结构中现有元素的算法。

16、算法类型

search

主要有两种类型的算法：搜索算法和排序算法。

搜索算法

为了从计算机内存中存在的大量数据中搜索特定的内存位置或特定值，我们使用搜索算法技术。

有各种类型的搜索技术，例如线性搜索、二进制搜索等。

排序算法

排序技术在数据结构中用于按特定顺序重新排列值。

顺序可以是增加、减少、不增加、不减少等。

17、总结

任何优秀的程序员都会在实现软件之前首先设计和分析软件。这就是为什么在实现特定问题的解决方案之前编写算法是首选方法的原因。这使得算法在解决计算问题方面非常重要。