在阅读本书的第一章时，你了解了各种数据类型。现在，是时候介绍算法这个主题了。在本章中，你将看到它们的定义，以及一些现实世界的例子、符号和类型。由于你需要关注应用程序的性能，算法的计算复杂性主题，包括时间复杂性，也将被介绍和解释。

首先，值得提到的是算法这个主题非常广泛和复杂。你可以在互联网上轻松找到大量关于它们的科学出版物，这些出版物由世界各地的研究人员发布。算法的数量是巨大的，几乎不可能记住所有常用算法的名称。当然，有些算法简单易懂且易于实现，而其他算法则极其复杂，没有算法学、数学和其他专业科学领域的深入知识几乎不可能理解。算法也有各种分类，根据不同的关键特征，有许多类型，包括递归、贪婪、分治、回溯和启发式。然而，对于各种算法，你可以通过说明它们随着处理输入大小增加所需的时间或空间来指定计算复杂性。

这听起来是不是令人畏惧、复杂和困难？别担心。在本章中，我将尝试以一种每个人都能理解的方式介绍算法主题，不仅仅是数学家或其他科学家。因此，在本章中，你会发现一些简化，使这个主题更简单、更容易理解。然而，目标是向你介绍这个主题并让你对算法产生兴趣，而不是创造另一本充满正式定义和公式的学术出版物或书籍。你准备好了吗？让我们开始吧！

在本章中，我们将涵盖以下主题：

• 什么是算法？

• 算法表示的符号

• 算法的类型

• 计算复杂性

什么是算法？

你知道你每天都在使用算法吗？而且即使没有编写任何代码或绘制任何图表，你已经成为了一些算法的作者。如果这听起来不可能，给我几分钟时间，读完这一部分，你会了解这是如何成为可能的。

定义

首先，你需要知道什么是算法。它是一个为解决特定问题或执行计算而定义良好的解决方案。它是一个有序的精确指令列表，这些指令按照给定的顺序执行，并考虑一个明确的输入（如果有的话），以产生一个明确的输出，如下所示:

更精确地说，算法应该包含一系列明确无误的指令，这些指令为你提供了一种有效且高效解决问题的方法。当然，算法可以包含条件表达式、循环或递归。

现实世界中的例子

掌握了算法的定义之后，你可能会想，“来吧——输入、输出、指令……我能在哪儿找到它们？”答案比你想象的要简单得多，因为几乎无处不在，无时无刻你都能找到这些元素！

让我们从一个简单的早晨例行程序开始。首先，你醒来并查看你的手机。如果有任何通知，你会浏览它们并回复紧急消息。对于任何不紧急的事项，你会推迟它们。然后，你去洗手间。如果它被占用，你会等到它空闲，告诉里面的人快点。一旦你进入洗手间，你就洗澡刷牙。最后，你根据当前的天气和温度选择合适的衣服。惊喜！你的早晨例行程序就是一个算法。你可以将其描述为一组指令，它有一些输入，比如通知和当前温度，以及输出，比如选择的衣服。更重要的是，其中一些指令是条件性的，比如只回复紧急消息。其他的可以循环执行，比如等待直到洗手间空闲。

前述的早晨例行程序还包含其他算法，比如使用面部识别解锁智能手机。这是一种基于算法的机制，你可以用来确保只有你能解锁你的手机。此外，即使在你的手机上组织通知也是算法的结果，它将通知作为输入，将它们分组，并在呈现给你之前适当地排序。

此时，你已经穿好衣服，准备好享用一顿健康美味的早餐了。想象一下，你想用你奶奶的秘密食谱来准备炒蛋。你需要一些食材，即三个鸡蛋、盐和胡椒。结果，你将为你的完美早餐创造一道美味的菜肴。首先，你将鸡蛋打入碗中，加入一点盐和胡椒搅拌。然后，在中低火上将黄油融化在一个不粘锅中。接下来，将鸡蛋混合物倒入锅中，并不断搅拌，直到没有液态的鸡蛋。这样，你的早餐就准备好了。然而，这不就是一个编写得当、组织有序的算法，它有一个精确的输入和美味的输出吗？

早餐后，你需要去工作。所以，你跳进你的车里，启动智能手机上的导航应用，查看到工作的最快路线，同时考虑到当前的交通状况。这项任务由复杂的算法执行，甚至可能涉及人工智能（AI），以及使用专门的数据结构的计算机可理解的路线表示，以及从其他用户那里获得的数据。当这些组合在一起时，就形成了交通数据。正如你所见，算法接受复杂的输入，并进行各种计算，以向你呈现一个有序的路线指令列表——例如，走A4路线，向右转到S19路线，然后沿着这条路线直到你到达目的地。

在工作中，你需要为会计准备文件，因此你需要从同事那里收集文件，从电子邮件中打印一些文件，然后按编号对所有发票进行排序。你是如何进行排序的呢？你从一堆文件中取出第一份文件放在桌子上。然后，你从未排序的堆中取出第二份文件，如果编号比第一份小，就放在它上面，否则放在它下面。接着，你取出第三份发票，并在已排序的堆中找到一个合适的位置放它。你重复这个操作直到未排序的堆中没有文件为止。哇，另一个算法？没错！这是排序算法之一。你将在下一章中学习它们。

工作时间到了，该休息一下了！你打开你最喜欢的社交应用，收到了添加新朋友的建议。然而，他们是如何被发现并推荐给你的呢？没错，你猜对了——这又是一个算法，它从你的个人资料和活动以及可用用户的数据中获取输入，并为你返回一系列最适合你的建议。它可以使用许多复杂和先进的技术，比如机器学习（ML）算法，这些算法可以学习并考虑你之前的反应。只需稍微思考一下，就可以知道在这种情况下可以使用哪些数据结构。你如何组织与朋友的关系，以及如何找出有多少其他人与你最喜欢的好莱坞演员之间有联系？如果知道你的朋友认识玛丽，玛丽认识亚当，而亚当是你偶像的朋友，那不是很棒吗？这样的任务可以使用一些基于图的结构来完成，正如你稍后在本书中看到的。

你将在这本书中学到关于AI算法的知识吗？

不幸的是，不会。由于页面数量有限，这本书没有包括与AI相关的各种算法。然而，请注意，这是一个非常有趣的话题，它涉及许多概念，比如机器学习（ML）和深度学习（DL），这些都被用于许多应用中，包括推荐系统、语音转文本、在大量数据上进行搜索（大数据的概念）、生成文本和图形内容，以及控制自动驾驶汽车。为了实现这些目标，使用了许多有趣的算法。我强烈鼓励你自己去研究这个话题，或者选择一本专注于AI相关主题的书。

这些例子足够了吗？如果不，想象一下在电影院选择一部电影时，考虑基于AI的电影推荐和基于地理位置的电影院数据，或者根据你第二天的计划设置闹钟。正如你所看到的，算法无处不在，我们所有人都在使用它们，即使我们没有意识到。

那么，如果算法如此普遍且有用，为什么我们不利用现有的大量算法，甚至编写我们自己的算法呢？还有一些问题需要通过算法来解决。作为本书的作者，我期待着你去解决这些问题！

算法表示的符号

在上一节中，算法是用文字呈现的。然而，这并不是指定和记录算法的唯一方式。在本节中，你将学习四种算法表示的符号，即自然语言、流程图、伪代码和编程语言。为了使这项任务更容易理解，你将用所有这些符号来指定计算算术平均值的算法。作为提醒，平均值可以使用以下公式计算:

正如你所见，使用了两个输入，即提供的数字（a）和元素的总数（n）。如果没有提供数字，将返回null，表示没有可用的平均值。否则，你将数字相加并除以元素的总数以得到结果。

自然语言

首先，让我们用自然语言来指定算法。这是一种提供关于算法信息的非常简单的方式，但它可能会含糊不清。所以，让我们这样描述我们的算法：

算法读取输入，这代表将要计算算术平均值的元素总数。如果输入的数字等于0，算法应返回null。否则，它应该读取等于预期总数的数字数量。最后，它应该返回结果，即数字之和除以它们的数量。

相当简单易懂，不是吗？你可以用这种符号来表示简单的算法，但对于复杂和高级的算法可能无用。当然，无论算法的复杂性如何，一些自然语言的描述通常都是有用的。它们可以给你一个关于算法目标、工作方式以及在分析或实现算法时应考虑哪些方面的简要理解。

流程图

另一种展示算法的方式是通过流程图。流程图使用一系列图形元素来绘制一个图表，该图表指定了算法的操作。可用的一些符号如下：

算法应包含入口点和一个或多个出口点。它还可以包含其他块，包括操作、输入、输出或条件。以下块通过箭头连接，指定了执行顺序。你还可以绘制循环。

让我们来看一个计算算术平均值的流程图：

执行开始于START块。然后，我们将0赋值给sum变量，该变量存储所有输入数字的总和。接下来，我们从输入读取一个值并将其存储为n变量的值。这是用于计算算术平均值的元素总数。接下来，我们检查n是否等于0。如果是，选择YES分支，将null返回到输出，并且执行停止。如果n不等于0，选择NO分支，我们将0赋值给i变量。它存储已从输入读取的元素数量。接下来，我们从输入读取一个数字并将其保存为a变量的值。接下来的操作块将sum的值增加a的值，并且增加i的值。

下一个代码块是一个条件判断块，它检查变量i是否不等于n，这意味着所需的元素数量尚未从输入中读取完毕。如果i等于n，程序将选择NO分支，并将结果变量的值设置为sum除以n的结果。然后，返回结果变量的值，并停止执行。当条件表达式评估为真时，即我们需要读取另一个输入时，使用了一个有趣的构造。然后，使用循环，并且执行回到读取a的输入块之前。因此，我们可以多次执行某些操作，直到满足条件为止。

正如你所见，流程图是一种图表，它使得以比使用自然语言更精确的方式指定算法操作成为可能。对于简单的算法来说，这是一个有趣的选择，但对于高级和复杂的算法来说，它可能相当繁琐，因为无法在一个合理大小的图表中展示整个操作过程。

伪代码

接下来我们要看的表示法是伪代码。它允许你以一种有点类似于编程语言中编写的代码的方式来指定算法。在这里，我们使用英语来定义输入和输出，以及清晰简洁地呈现一组指令，但不使用任何编程语言的语法。

以下是一些计算算术平均值的伪代码示例：

INPUT:n – 用于平均值计算的元素总数。a – 用户输入的以下数字。OUTPUT:result - 输入数字的算术平均值。INSTRUCTIONS:sum <- 0read nif n = 0 then return nullendifi <- 0do   read a	 sum <- sum + a	 i <- i + 1while i <> nresult <- sum / nreturn result

正如你所见，伪代码为我们提供了一种易于理解和遵循的语法，同时也非常接近编程语言。因此，它是算法呈现和文档记录的一种精确方式，之后可以将其转换为我们选择的编程语言的一系列指令。

编程语言

现在，让我们来看算法表示的最后一种形式：编程语言。它非常精确，可以被编译和运行。因此，我们可以看到其操作的结果，并使用一组测试用例进行检查。

当然，我们可以在任何编程语言中实现算法。然而，在这本书中，你将只看到C#语言中的示例。

让我们来看一下平均值计算算法的实现：

double sum = 0;Console.Write("n = ");int.TryParse(Console.ReadLine(), out int n);if (n == 0) { Console.WriteLine("No result."); }int i = 0;do{    Console.Write("a = ");    double.TryParse(Console.ReadLine(), out double a);    sum += a;    i++;}while (i != n);double result = sum / n;Console.WriteLine($"Result: {result:F2}");

前面的代码包含了一个if条件语句和一个do-while循环。

如果我们运行应用程序，我们需要输入我们想要计算算术平均值的元素数量。然后，我们将被要求输入n次数字。当提供的元素数量等于预期值时，结果将被计算并以如下方式呈现在控制台上：

n = 3a = 1a = 5a = 10Result: 5.33

就这样！现在，你知道算法是什么，你可以在日常生活中在哪里找到它们，以及如何使用自然语言、流程图、伪代码和编程语言来表示算法。有了这些知识，让我们继续学习不同类型的算法，包括递归和启发式算法。