本文转载自微信公众号《大数据DT（ID：hzdashuju）》，作者帕诺斯·劳里达斯（PanosLouridas）。转载本文请联系大数据DT（ID：hzdashuju）公众号。算法（algorithm）是一个过程，是一个特殊的过程。它必须被描述为一个有限的步骤序列，并且必须在有限的时间内结束。每个步骤都必须明确定义到人类可以用一支笔和一张纸来执行的程度。算法根据我们给它的输入做一些事情，并产生一些反映它所做工作的输出。算法1-1实现了我们之前描述的过程。算法1-1一个简单的股票跨度算法SimpleStockSpan(quotes)→spans输入：quotes，一个存储n个股票报价的数组输出：spans，一个存储n个股票的数组spans←CreateArray(n)fori←0tondok←1span_end←FALSEwhilei-k≥0并且notspan_enddoifquotes[i-k]≤quotes[i]thenk←k+1elsespan_end←TRUEspans[i]←kreturnspans算法1-1展示了如何描述该算法。我们不使用计算机语言，因为那会迫使我们处理与算法逻辑无关的实现细节，我们使用一种伪代码形式。伪代码是介于真实程序代码和非正式描述之间的一种形式。它使用结构化格式并使用一组具有特定含义的词。但是，伪代码不是真正的计算机代码。它不是为了由计算机执行，而是为了让人类更容易理解。顺便说一句，程序也应该是人类可以理解的，但并不是所有的程序都是这样——有很多运行中的计算机程序写得不好而且很难理解。每个算法都有一个名称，接受一些输入，并产生一些输出。在本书中，算法的名称将以CamelCase形式书写，输入将写在括号中，输出将以→表示。接下来的几行描述了算法的输入和输出。可以使用算法名称调用算法，后跟用括号括起来的输入。一旦编写了一个算法，它就可以被视为一个黑盒子，可以给它一些输入，黑盒子将返回算法的输出。当算法以编程语言实现时，它是一段命名的计算机代码——一个函数。在计算机程序中，我们调用实现算法的函数。有些算法不产生输出，当然也不会显式返回结果。相反，他们的行为会影响上下文的某些部分。例如，我们可以给算法一个空间来写它的结果。在这种情况下，算法不会返回传统意义上的输出，但算法无论如何都有输出，即它会影响上下文的变化。某些编程语言区分显式返回结果的命名程序代码段（称为函数）和不返回结果但可能具有其他副作用的命名程序代码段（称为过程）。这种差异来自数学，数学函数必须返回值。对我们来说，当算法被编码为实际程序时，它既是函数又是过程。我们的伪代码使用了一些粗体关键字，如果您对计算机和编程语言的工作原理有所了解，其含义应该是不言自明的。我们用字符←表示赋值，用等号（=）表示相等比较。我们用常用的五个符号（+、-、/、×、·）来表示四种数学运算，最后两个符号表示乘法。我们将使用这两个符号并根据审美考虑进行选择。我们不会使用任何关键字或符号来对伪代码进行分块，分块以缩进表示。在这个算法中，我们使用数组。数组是一种保存数据并允许我们以特定方式操作其中数据的结构。我们保存数据并允许对其保存的数据执行特定操作的结构称为数据结构。所以数组是一种数据结构。数组之于计算机就像对象序列之于人类。数组是存储在计算机内存中的有序元素序列。要获得容纳元素所需的空间并创建一个包含n个元素的数组，请在算法1-1的第1行中调用CreateArray算法。如果您熟悉数组，您可能想知道创建数组为何需要一种算法。但这是真的。为了得到一块内存来保存数据，你至少得在计算机上搜索可用的内存，并标记为数组。CreateArray(n)调用完成它需要做的一切，它返回一个包含n个元素的数组，最初没有元素，只有容纳元素所需的空间。该算法负责调用CreateArray(n)将实际数据填充到数组中。对于数组A，我们用A[i]表示它的第i个元素，这个符号也用来访问这个元素。数组中元素的位置，例如A[i]中的i，称为索引。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”。总而言之，数组是一种数据结构，它包含一系列相同类型的项目。数组支持两种操作：CreateArray(n)创建一个可以容纳n个元素的数组。一个数组是未初始化的，即它不保存任何实际元素，但保存元素所需的空间是保留的，可以用来保存元素。正如我们所见，对于数组A，访问A[i]的第i个元素所花费的时间与访问数组中的任何元素所花费的时间相同。如果i<0，尝试访问A[i]将产生错误。我们回到算法1-1。前面说过，算法的第2行到第10行是一个循环，也就是重复执行的一段代码。如果我们有n天的行情，循环执行n次，每次计算一个span。变量i代表我们正在计算跨度的当天。一开始是第0天最早的时间点，每执行到第2行，循环就前进到第1、2、...、n-1天。我们使用一个变量（variable）k来表示当前跨度的长度——在我们的伪代码中，一个变量是一个名称，它指的是一些数据，这些数据的内容，或者更准确地说，是变量的值（value），在算法可以在执行过程中改变，因此术语变量。当我们开始计算一个跨度时，k的值始终为1，我们在第3行设置了这个初始值。我们还使用了一个指示变量span_end。指示变量取值TRUE或FALSE，表示某事是真还是假。当我们到达跨度的末尾时，变量span_end的值将为真。span_end在开始计算每个跨度时为假，如第4行所示。第5-9行的内循环计算跨度的长度。第5行告诉我们回溯尽可能长的时间，只要span还活着。我们能回到多远是由条件i-k≥0决定的：回到索引i-k指示的那一天检查跨度是否结束，并且索引不能为0，因为0对应第1天。第6行检查到查看跨度是否结束。如果span没有结束，它的长度在第7行增加。否则，我们注意到第9行设置了span的结束，以便循环在返回到第5行后终止。当第2到10行的外层循环结束时在第10行循环，我们将k的值保存到此处数组span的正确位置。在退出循环后的第11行，我们返回spans，它保存着算法的结果。请注意，最初我们设置i=0和k=1。这意味着第5行的条件必须尽早为假。这是应该的，因为第0天只能有1个跨度。现在，请记住我们所说的算法、笔和纸。理解算法的最好方法是手动执行它。每当算法看起来很复杂，或者您不确定自己是否完全理解它时，请拿笔和纸写下实现它的过程以解决一个例子。这种方法会为你节省很多时间，尽管它看起来有点老套。如果你对算法1-1还不清楚，请立即尝试这个方法，等算法完全清楚后再回来。作者简介：PanosLouridas拥有曼彻斯特大学软件工程博士学位，现任雅典经济贸易大学管理科学与技术系副教授。在加入大学之前，他曾在一家投资银行担任高级软件工程师。本文节选自《真实世界的算法：初学者指南》，经发布者授权发布。
