初学者指南：什么是算法？11行伪代码给你讲明白

Bertha 。 2022-12-01 15:45 136阅读 0赞

![format_png][]

**导读：**本文带你熟悉一个重要的术语——算法。

作者：帕诺斯·卢里达斯（Panos Louridas）

来源：大数据DT（ID：hzdashuju）

![format_png 1][]

**算法**（algorithm）就是一个过程，是一种特殊的过程。它必须描述为一个有限步骤序列，且必须在有限时间内结束。每个步骤必须是良好定义的，达到人类可用一支笔和一张纸执行它的程度。

算法基于我们提供给它的输入做一些事情，并生成反映其所做工作的一些输出。算法1-1实现了我们前面描述的过程。

*  **算法1-1 一个简单的股票跨度算法**

SimpleStockSpan(quotes)→spans

*  输入: quotes,保存n个股票报价的数组
 *  输出: spans,保存n个股票跨度的数组

1spans←CreateArray(n)
     2for i←0 to n do
     3    k←1
     4    span_end ← FALSE
     5    while i-k ≥ 0 and not span_end do
     6       if quotes[i-k] ≤ quotes[i] then
     7           k←k+1
     8       else
     9           span_end ← TRUE
    10    spans[i] ← k
    11return spans

算法1-1展示了如何描述算法。我们并不使用某种计算机语言，因为那样会迫使我们处理与算法逻辑无关的实现细节，我们使用的是某种**伪代码**（pseudocode）形式。

伪代码是一种介于真正的程序代码和非形式化描述之间的形式。它使用一种结构化格式，并采用一组具有特定含义的词汇。但是，伪代码不是真正的计算机代码。它并不是为了被计算机执行，而是易于被人类理解。

顺便提一下，程序也应能被人类理解，但并非所有程序都是如此——有很多正在运行的计算机程序写得很糟糕，难以理解。

每个算法都有一个名字，接受一些输入，并生成一些输出。在本书中，算法的名字将采用**骆驼拼写法**（CamelCase），输入会写在括号中，输出用一个→指示。接下来的几行将会对算法的输入和输出进行描述。可以用算法的名字紧接放在括号中的输入来**调用**（call）算法。

一旦算法编写好，就可以将其作为一个黑盒来处理，可以给它一些输入，黑盒则会返回算法的输出。当用一种程序设计语言实现一个算法时，它就是一个具名的计算机代码片段——**函数**（function）。在一个计算机程序中，我们调用实现算法的函数。

某些算法不生成输出，当然也就不会显式返回结果。取而代之的是，它们的行为影响上下文的某部分。例如，我们可能提供给算法一个空间，供其写入结果。在此情况下，在传统意义上算法并非返回输出结果，但无论如何算法是有输出的，即它影响上下文发生的变化。

某些程序设计语言会区分显式返回结果的具名程序代码片段——称为**函数**（function），以及不返回结果但可能有其他副作用的具名程序代码片段——称为**过程**（procedure）。这种差异来源于数学，数学上的函数是必须返回值的。对我们来说，当一个算法编码为实际程序时，既可以是一个函数也可以是一个过程。

我们的伪代码中使用一些用粗体表示的关键字，如果你对计算机和程序设计语言的工作方式有所了解，这些关键字的含义就是不言自明的了。

我们使用字符←表示赋值，用等号（=）表示相等比较。我们采用常用的五个符号（+，-，/，×，·）表示四种数学运算，后两个符号都表示乘法，这两个符号我们都会使用，基于美学考虑进行选择。我们将不会使用任何关键字或符号对伪代码分块，分块是通过缩进来表示的。

在这个算法中，我们使用了**数组**（array）。数组是一种保存数据的结构，它允许我们按特定方式操纵其中的数据。我们保存数据并允许在其保存的数据上执行特定操作的结构称为**数据结构**（data structure）。因此数组是一种数据结构。

数组之于计算机，就像对象序列之于人类。数组是元素的有序序列，这些元素存储在计算机内存中。为了获得保存元素所需的空间并创建一个保存n个元素的数组，可调用算法1-1第1行中的CreateArray算法。

![format_png 2][]

如果你熟悉数组，可能就会奇怪创建数组怎么还需要一个算法。但实际情况的确如此。**为了获得保存数据的一块内存，你必须至少在计算机中搜索可用内存并标记它为数组所用。**

CreateArray(n)调用做了所需的一切，它返回一个可容纳n个元素的数组，初始时其中没有元素，只有保存元素所需的空间。算法负责调用CreateArray(n)来将实际数据填充到数组中。

对数组A，我们用A\[i\]表示其第i个元素，访问该元素也是用该符号。一个元素在数组中的位置，如A\[i\]中的i，被称为**索引**（index）。一个n个元素的数组A包含元素A\[0\]，A\[1\]，…，A\[n-1\]。

这可能令你吃惊，因为**其首元素是第0个，而尾元素是第n-1个**，可能你的预期是第1个和第n个。但是，大多数计算机语言中的数组都是如此，你最好现在就熟悉这种机制。这非常常见，当遍历一个大小为n的数组时，我们是从位置0遍历到位置n-1。

在我们的算法中，当我们说某个对象的取值是从数x到数y（假定x小于y）时，意思是从x到y（但不包含）的所有值，参见算法第2行。

我们假定无论i的值是什么，访问第i个元素都花费相同的时间。因此访问A\[0\]与访问A\[n-1\]需要相同的时间。这是数组的一个非常重要的特性：**对元素的访问是一致的，都花费常量时间。**当我们通过索引访问数组元素时，数组不需要搜索此元素。

关于算法描述中的符号表示，我们用小写字母表示算法中的变量。但当变量表示一个数据结构时，我们会使用大写字母来令其突出，如数组A。但这并非必要。当我们希望给变量起一个包含很多单词的名字时，我们会使用下划线（\_），如a\_connector。**这是必要的，因为计算机不理解由一组空格分隔的单词构成单个变量名的方式。**

算法1-1使用数组保存数值。数组可以保存任何类型的项，在我们的伪代码中每个数组只能保存单一类型的项。大多数程序设计语言中也都是如此。

例如，可以创建十进制数数组、分数数组、表示人的项的数组以及另一个表示地址的项的数组，但不可以创建一个既包含十进制数又包含表示人的项的数组。至于“表示人的项”会是什么，由编程所使用的语言所决定。所有程序设计语言都提供表示有意义的东西的方法。

一种特别有用的数组是字符数组。一个字符数组表示一个字符串（string），即一个字母序列、一个数序列、一个单词序列、一个句子序列等。与所有数组一样，我们可以用索引单独引用数组中的单个字符。如果我们有一个字符串s=“Hello，World”，则s\[0\]为字母“H”而s\[11\]为字母“d”。

![format_png 3][]

总结一下，数组就是一个保存相同类型项的序列的数据结构。**数组支持两种操作：**

*  CreateArray(n)创建一个能保存n个元素的数组。数组未初始化，即它不保存任何实际元素，但保存元素所需的空间已预留，可用来保存元素。
 *  正如我们已经看到的，对一个数组A，A\[i\]访问其第i个元素，而且访问数组中任何元素都花费相同时间。若i＜0，则试图访问A\[i\]会产生错误。

我们回到算法1-1。如前所述，算法第2～10行是一个循环，即一个反复执行的代码块。如果我们有n天的报价的话，循环执行n次，每次计算一个跨度。变量i表示我们正在计算跨度的当前这一天。初始时，处于第0天这一最早的时间点。每次执行第2行代码时，就会推进循环到第1，2，…，n-1天。

我们使用**变量**（variable）k指示当前跨度的长度——在我们的伪代码中，变量就是一个引用某些数据的名字，那些数据的内容，或者更精确地说，变量的**值**（value），在算法执行的过程中是可以改变的，变量这个术语因而得名。当我们开始计算一个跨度时，k的值总是1，我们是在第3行设置这个初值的。

我们还使用了一个**指示变量**（indicator variable）span\_end。指示变量取值TRUE或FALSE，指出某事成立或不成立。当我们到达一个跨度的末端时，变量span\_end的值将为真。

在开始计算每个跨度时，span\_end为假，如第4行所示。第5～9行的内层循环计算跨度的长度。第5行告诉我们，只要跨度还未结束，就回退尽可能长的时间。我们能回退多远由条件i-k≥0决定：回退到索引i-k指示的这一天检查跨度是否结束，而索引不能为0，因为0对应第1天。

第6行检查跨度是否结束。如果跨度未结束，则在第7行增加其长度。否则，我们注意到，第9行设置跨度结束，从而循环会在回到第5行后终止。

第2～10行的外层循环在第10行结束一次循环时，我们在此将k的值保存到数组spans的正确位置。在退出循环后的第11行，我们返回spans，它保存着算法的结果。

注意，初始时我们设定i=0和k=1。这意味着在最早的时刻第5行的条件必定为假。这是理所应当的，因为第0天的跨度只能为1。

此时此刻，记住我们曾说过的关于算法、笔和纸的内容。理解一个算法的最好方法就是去手动执行它。

在任何时候如果一个算法看起来有些复杂，或者你不确定是否已完全理解它，**就用纸和笔写下执行它求解某个例子的过程。**这种方法会节省你很多时间，虽然它看起来有点老套。如果对算法1-1还有不明确的地方，马上尝试这种方法，当算法已完全清晰后再回到这里。

关于作者：帕诺斯·卢里达斯（Panos Louridas），曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授。在加入高校之前，曾在投资银行担任高级软件工程师。

本文摘编自《真实世界的算法：初学者指南》，经出版方授权发布。

延伸阅读《真实世界的算法：初学者指南》

点击上图了解及购买

转载请联系微信：DoctorData

**推荐语：**学习算法的启蒙读本，算法尽量简单，避免读者有挫败感，仅需基本数学基础和计算机常识知识。通过真实世界需要解决的实际问题来介绍算法思想，为各领域高效运用算法提供重要指南。

![音符][format_png 4]

**划重点????**

**干货直达????**

*  [6大人工智能应用关键技术，终于有人讲明白了][6]  
    
 *  [西安交大送大一新生这本书，你读过吗？12本有趣有料的科普书盘点][12]  
    
 *  [终于有人把AI、BI、大数据、数据科学讲明白了][AI_BI]  
    
 *  [监督学习、非监督学习、强化学习都是什么？终于有人讲明白了][Link 1]

**更多精彩????**

在公众号对话框输入以下**关键词**

查看更多优质内容！

**PPT** | **读书** | **书单** | **硬核** | **干货**** **| **讲明白 **|** 神操作**

**大数据** | **云计算** | **数据库** | **Python** | **可视化**

**AI** | **人工智能** | **机器学习** | **深度学习** | **NLP**

**5G**** **|** 中台 **|** 用户画像**** **| **1024** | **数学 **|** 算法 **| **数字孪生**

据统计，99%的大咖都完成了这个神操作

**????**

![format_png 5][]

![format_png 6][]

[format_png]: /images/20221123/1fad41e122e6488a93629ecb08929fda.png
[format_png 1]: /images/20221123/154d544ba7a64820bcfe1c2ca3b2e00f.png
[format_png 2]: /images/20221123/737b810c3ece4171b9a541d8e0660798.png
[format_png 3]: /images/20221123/fd23691df2ec48438c0618e01d53e4b9.png
[format_png 4]: /images/20221123/b719c36f5a5b4ea8af132256c0629fa4.png
[6]: http://mp.weixin.qq.com/s?__biz=MzI5OTk5OTM2Mw%3D%3D&chksm=ec8cf819dbfb710fe8cac56256c49b0ecfa81fefc6744d888897822be32fe940ddc310b3384d&idx=1&mid=2247512565&scene=21&sn=afc7965e5a13417026fdd34c4af0b33d#wechat_redirect
[12]: http://mp.weixin.qq.com/s?__biz=MzI5OTk5OTM2Mw%3D%3D&chksm=ec8cf987dbfb70910f863ce3a4905d8096624b53cddfa187efce694b2520950e4752d6b33e60&idx=2&mid=2247512171&scene=21&sn=13f9d27be53366595cec0df2da9af1a5#wechat_redirect
[AI_BI]: http://mp.weixin.qq.com/s?__biz=MzI5OTk5OTM2Mw%3D%3D&chksm=ec8cf9f1dbfb70e74557be6901f6afd6624101f330e4ac2f4fb520ce1b7e53ca34a330c5ac8e&idx=2&mid=2247512093&scene=21&sn=7cb3f54732590512cb3ae1343c0f0684#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzI5OTk5OTM2Mw%3D%3D&chksm=ec8ce6dfdbfb6fc95b65ccea4d84b02d4660221fecfca23eef010ee6e78955e1fe2fb62a7569&idx=2&mid=2247511859&scene=21&sn=7264324e69991e55edff57b1da07768d#wechat_redirect
[format_png 5]: /images/20221123/7d6ce8fd88e54799ac351b88aa2bdc25.png
[format_png 6]: /images/20221123/80ecfe83d3e34b6093d1b6b589db102f.png