《算法基础:打开算法之门》一2.1 如何描述计算机算法

简介:

本节书摘来自华章出版社《算法基础:打开算法之门》一书中的第2章,第2.1节,作者 [美]托马斯 H 科尔曼(Thomas H Cormen),更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.1 如何描述计算机算法

将计算机算法描述成一个可执行程序可以有多种选择,例如使用通用的编程语言表示,像Java、C、C++、Python或Fortran。诚然,许多教科书上的算法都是这么表示的。但是使用实际的编程语言来表示算法所带来的问题是你可能会在语言细节上越陷越深,而对算法本身的认识反而模糊不清。另一种表示算法的方式是“伪代码”,就像我们在《算法导论》中使用的一样,它听起来像是多种编程语言和英语的混合表示。如果你曾用一种实际的编程语言编写过程序,那么你就能很容易地搞清楚伪代码。但是如果你从来没有编写过程序,那么对你而言,伪代码可能是带些神秘感的。

本书中我所采取的描述算法的方式并不是将算法描述在硬件或者软件上,而是描述在“湿件”上,即类似耳朵间的灰质。我也假定你从没编写过一个计算机程序,所以我不会使用任何实际的编程语言或者是伪代码来表示算法。反之,我将用通用的文字来描述算法,尽可能地使用现实世界中的情境来模拟算法。为了表示发生的事(编程中我们称之为“控制流”),我将使用列表和嵌套列表方式表示。10如果你想在一个实际的编程语言中实现算法,并能将我的描述转化为可执行代码,我将为此给你加分。

虽然我会尽可能地以一种通用的、非技术的方式描述算法,但是本书本身是关于计算机算法的,所以必定会涉及计算技术。例如,计算机程序包含程序(procedures,也称为实际编程语言中的函数或方法),它用来指定如何执行步骤。为了真正实现假定要执行的程序,我们调用它。当调用一个程序时,我们需要提供输入(通常一个程序至少包含一个输入,但是有些程序不需任何输入)。这些输入被称为参数,位于程序名之后的括号内。例如,为了求一个数的平方根,可以定义一个程序为SQUAREROOT(x);这里,程序的输入是参数x。任何被调用程序可能会产生输出,也可能不会产生输出,这取决于如何指定程序。如果程序产生输出,通常我们认为输出是返回给调用者的。计算术语中称作程序返回了一个值。

许多程序和算法都对数组进行操作。数组是将类型相同的数据聚集成一个实体。你可以把数组看作一个表格,给定表格中一个条目的索引,我们就可以访问该索引所指数组中的元素。例如,以下是一个由美国前5位总统组成的表格。
image

例如,表中索引为4的元素是James Madison。我们并不将该表看作是5个独立的实体,而是将它们看作是由5个条目所组成的一个表。

数组和表类似。数组中的索引是可从任意值开始的连续数字,但是我们通常将索引设为从1开始。如果你用Java、C,或者C++编程,那么你会习惯于令数组索引从0开始。对于计算机而言,令数组索引从0开始是很好的,但是对于湿件(硬件、软件以外的“件”,即人脑)而言,通常直觉上习惯从1开始。给定数组名和索引,我们用方括号将它们组合起来以表示一个特定的数组元素。例如,我们将数组A的第i个元素表示为A[i]。11数组还有另外一个重要的特性:访问数组中的任意元素均会花费同样长的时间。一旦你指定数组中的一个索引i,那么计算机能像访问第一个元素那样,以同样时间迅速地获取第i个元素,即速度与i值无关。让我们看看我们的第一个算法:在数组中查找一个特定的值。也就是说,给定一个数组,我们想知道数组中哪个条目或者哪些条目等于给定的值。为了观察在数组进行查找操作的过程,我们将数组看作是一个装满书的长长的书架,并且假定你想知道书架上哪个位置可以找到一本由Jonathan Swift写的书。现在,书架上的书可以以某种方式陈列,可以按作者名的字母顺序排序,也可以按书名的字母顺序排序,或者像图书馆中按图书的书号顺序陈列。这个书架也可以像我自家的书架一样,并没有按照任何特定的方式陈列着。如果假定书架上的书并没有以某种特定顺序陈列,那么你如何查找到由Jonathan Swift写的书呢?这便是我要讲解的算法。我将从书架的最左侧开始查找,并查看这本书是否是Swift写的。如果它是Swift写的书,那么我便找到了这本书。如果它不是Swift写的书,那么我将继续向右查找,依次向右查看当前的书是否是Swift写的,一直到找到Swift写的书或者已经查找到了书架的最右侧,在查找到书架的最右侧这种情况下,我就可以断定书架上没有Jonathan Swift写的任何书。(在第3章中,我们将看到当书架上的书按某种顺序陈列时,我们是如何进行查找的。)下面将该查找问题描述为一个计算问题。我们将书架上的书看作是以书为元素的数组。最左侧的书位于位置1处,该书右侧的书位于位置2处,以此类推,如果书架上有n本书,那么最右侧的书就位于位置n处。我们想要查找由Jonathan Swift所写的任意一本书在书架上所处的位置。作为一个泛化的计算问题,即给定一个具有n个元素(每本书)的数组A(要查找装满书的整个书架),我们想要查找数组A中是否存在一个值x(一本由Jonathan Swift所写的书)。如果存在,那么我们想要确定满足A[i]=x(一本由Jonathan Swift所写的书在书架上的位置i)的索引i的值。同时,我们也需要一些方法来表明数组A中不存在x(书架上不包含由Jonathan Swift所写的书)。我们并不假定x在数组中最多出现一次(可能你某些书有多本),12因此如果数组A中存在x,x可能会出现多次。我们想要从一个查找算法中得到的是数组中能够得到元素x的任意一个索引值。我们将假定该数组中索引从1开始,因此它的元素是从A[1]到A[n]。如果查找由Jonathan Swift所写的书是从最左侧开始查找,依次向右检查当前书是否是由Jonathan Swift所写,该方法被称为线性查找。计算机中的线性查找等价于:从数组的开始端开始查找,依次检查每个数组元素(A[1],A[2],A[3]…A[n]),若找到x,则记录下x所在的位置。下面这个线性查找程序(LINEARSEARCH)以3个参数作为输入,各参数之间以逗号隔开(规范表示)。

image

除了参数A、n和x之外,LINEARSEARCH程序还使用一个称为answer的变量。这个程序在第1步将answer赋值为NOTFOUND。第2步逐步检查A[1]到A[n]项并判断该项是否等于值x。当A[i]等于x时,第2A步将answer赋值为当前的i值。如果数组中包含x,那么第3步会返回输出值,即最后一次出现x的索引位置。如果数组中不包含x,那么第2A步的等式始终不成立,那么最后返回的输出值是NOTFOUND,即第1步中answer被赋予的值。在继续讨论线性查找之前,需说明一个词,即如何指定重复操作,例如程序的第2步。这种对一个变量在一定范围内取各种值的操作在算法中非常常见。当我们执行重复操作时,我们称它为一个循环,并且我们将每次循环操作称为循环的一次迭代。对于第2步的循环,13我写道“For each index i,going from 1 to n,in order”(对每个索引值i,按顺序从1取到n)。取而代之,之后我将简写为“For i= 1 to n”,该语句与上一句表示相同的意思。请注意,当我以这种方式写循环时,我们必须给循环变量(这里指i)指定一个初始值(这里是1),并且在循环的每次迭代过程中,我们必须判断循环变量的值是否超界(这里界是n)。如果当前循环变量的值小于或等于这个界,那么我们就执行循环主体(这里指第2A步)。当执行完循环主体的一次迭代后,我们就增加循环变量的值——将循环变量的值自增1——再返回循环条件判断那步,此时将更新的循环变量和界进行比较,再次执行循环体,并增加循环变量的值,直到循环变量超界为止。之后执行操作转到紧接着循环体的那步(这里指第3步)。形为“For i=1 to n”的循环执行n次迭代和n+1次判断是否越界的操作(因为循环变量在第n+1次测试比较时越界)。希望你能很清楚地发现LINEARSEARCH程序总能返回一个正确的结果。然而,你可能也注意到,这个程序不够高效:即使它已经找到了一个令A[i]=x成立的索引i,它还会继续在数组中查找x。通常情况下,一旦你在书架上找到了你要找的书,你就不会再继续再找那本书了。因此,我们可以设计出另外一个线性查找程序(BETTERLINEARSEARCH),使得一旦在数组中找到x,它便会停止查找。我们假定当我们说返回一个值时,程序会立即将该值返回给起控制作用的调用者。
image

信不信由你,我们能设计出更高效的线性查找算法。观察一下,BETTERLINEARSEARCH程序每进行第1步的循环时,会做出两个测试:一个测试是在第1步,用来测试i≤n是否成立(如果成立,执行循环的又一次迭代);另一个测试是第1A步的“是否相等”的判断。类似在书架上查找书这个例子,这两个测试相当于你必须对每本书做两个判断操作:14你现在查找到书架的末端了吗?如果没有,下本书是不是Jonathan Swift写的呢?当然,如果你查找时越过了书架的末端,也不会造成巨大的损失(除非在你查找过程中,你的脸离书太近,以至于当你到达在书架的末端时,你的脸会撞到书架末端的墙上),但是在计算机程序中,当你试图访问越过数组末尾的元素时,结果通常是糟糕的。你的程序可能会崩溃,也可能会损坏数据。如果你不确定书架上是否包含Jonathan Swift所写的书,为了避免访问越界,你须对每本书执行一次检查操作。要是你确定书架上包含Jonathan Swift的书又如何呢?那么你就可以放心地查找它了,而且你从不必担心会检查到超过书架末端书的位置。你仅仅需要依次检查当前这本书是否是Swift写的即可。但是有可能你将Jonathan Swift所写的书都借出去了或者也有可能你以为你的书架上有Jonathan Swift写的书,但是实际上并没有,所以你并不能确定你的书架上是否包含Jonathan Swift写的书。这时你可以将最右边的书替换成一个跟书大小一样的空盒子且在它的窄边(即书脊位置)写上“Gulliver’s Travels by Jonathan Swift”。那么,当你沿着书架从左向右查找书时,你仅仅需检查当前这本书是否是Jonathan Swift写的。你不需要再检查你是否越过了书架的最右侧,因为你知道你一定会找到Jonathan Swift所写的书。唯一的问题是你是否真的找到了Swift所写的书,还是你找到了那个被标记为Jonathan Swift所写的空盒子?如果你找到了空盒子,那么你并不是真的有一本由Swift所写的书。那么,你需要做的事情很简单,你仅仅需在查找的最后再添加一次对最右边那本书的检查操作,而不必添加对书架上的每本书均再检查一遍的操作。这里还有一个细节必须注意:要是书架上仅有的一本由Jonathan Swift所写的书就是放在书架最右端呢?如果你将这本书替换成了空盒子,那么你的查找会终止于空盒子,你可能得出你没有Jonathan Swift所写的书的结论。所以你必须针对这种可能性再进行一次检查操作,但这也仅仅是对一本书进行一次检查,而不是对书架上的每本书均进行一次检查。转化为计算机算法,即是先将最后一个位置的元素A[n]的内容保存到一个变量中,再将要查找的值x赋值给A[n]。15一旦找到了x,就可以验证我们是否真正找到了x。其中,x被称作信号量,你也可以将它看成空盒子。

image
image

第3步是一个循环,但是循环变量实际取的值并非循环变量可取范围内的所有值。反之,只有当循环条件成立时,循环迭代才会执行;这里,循环条件是A[i]≠x。执行这个循环相当于首先执行判断(这里指代A[i]≠x),之后如果条件成立,那么才能执行循环体的内容(这里,指第3A步,即i值自增1)。然后返回到再次执行循环条件判断部分,即第3步,如果条件成立,则执行循环体。循环迭代中,首先测试条件是否成立,然后执行循环体,直到条件不成立时结束循环。然后执行紧接循环体的步骤(这里指第4步)。SENTINELLINEARSEARCH程序相对于前两个查找程序而言略显复杂。因为它首先在第1步中将x赋值给A[n],这样我们确保了当执行到i=n时,必有A[i]等于x成立(第3步)。一旦A[i]=x成立,那么第3步的循环必定可以结束,且随后索引i的值不会再改变。在继续执行其他操作前,第4步又将A[n]的原始初值重新赋给了A[n]。(正如妈妈教导我的,玩耍完后,要将所有物品物归原位。)随后我们需要判定是否在数组中真的找到了x。由于第1步,A[n]被赋为x,可以得知如果我们发现A[i]=x且i

相关文章
|
23天前
|
机器学习/深度学习 算法 TensorFlow
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现用户上传一张动物图片,识别其名称。
53 1
动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目
|
21天前
|
机器学习/深度学习 算法 TensorFlow
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高的模型文件,然后保存为本地的h5格式文件。再使用Django开发Web网页端操作界面,实现用户上传一张交通标志图片,识别其名称。
47 6
交通标志识别系统Python+卷积神经网络算法+深度学习人工智能+TensorFlow模型训练+计算机课设项目+Django网页界面
|
17天前
|
机器学习/深度学习 人工智能 算法
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
文本分类识别系统。本系统使用Python作为主要开发语言,首先收集了10种中文文本数据集("体育类", "财经类", "房产类", "家居类", "教育类", "科技类", "时尚类", "时政类", "游戏类", "娱乐类"),然后基于TensorFlow搭建CNN卷积神经网络算法模型。通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型,并保存为本地的h5格式。然后使用Django开发Web网页端操作界面,实现用户上传一段文本识别其所属的类别。
42 1
【新闻文本分类识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
1月前
|
前端开发 搜索推荐 算法
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
中草药管理与推荐系统。本系统使用Python作为主要开发语言,前端使用HTML,CSS,BootStrap等技术和框架搭建前端界面,后端使用Django框架处理应用请求,使用Ajax等技术实现前后端的数据通信。实现了一个综合性的中草药管理与推荐平台。具体功能如下: - 系统分为普通用户和管理员两个角色 - 普通用户可以登录,注册、查看物品信息、收藏物品、发布评论、编辑个人信息、柱状图饼状图可视化物品信息、并依据用户注册时选择的标签进行推荐 和 根据用户对物品的评分 使用协同过滤推荐算法进行推荐 - 管理员可以在后台对用户和物品信息进行管理编辑
58 12
中草药管理与推荐系统Python+Django网页界面+推荐算法+计算机课设系统+网站开发
|
17天前
|
机器学习/深度学习 人工智能 算法
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台。果蔬识别系统,本系统使用Python作为主要开发语言,通过收集了12种常见的水果和蔬菜('土豆', '圣女果', '大白菜', '大葱', '梨', '胡萝卜', '芒果', '苹果', '西红柿', '韭菜', '香蕉', '黄瓜'),然后基于TensorFlow库搭建CNN卷积神经网络算法模型,然后对数据集进行训练,最后得到一个识别精度较高的算法模型,然后将其保存为h5格式的本地文件方便后期调用。再使用Django框架搭建Web网页平台操作界面,实现用户上传一张果蔬图片识别其名称。
37 0
【果蔬识别系统】Python+卷积神经网络算法+人工智能+深度学习+计算机毕设项目+Django网页界面平台
|
23天前
|
机器学习/深度学习 存储 人工智能
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
使用Python作为开发语言,基于文本数据集(一个积极的xls文本格式和一个消极的xls文本格式文件),使用Word2vec对文本进行处理。通过支持向量机SVM算法训练情绪分类模型。实现对文本消极情感和文本积极情感的识别。并基于Django框架开发网页平台实现对用户的可视化操作和数据存储。
26 0
文本情感识别分析系统Python+SVM分类算法+机器学习人工智能+计算机毕业设计
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
探索计算机人工智能算法
在信息科技飞速发展的今天,人工智能(AI)炙手可热。计算机AI算法作为核心,使系统能模拟乃至超越人智。本文探索AI算法原理,涵盖机器学习(监督与无监督学习)、深度学习及自然语言处理等关键技术,展示其如何通过数据分析、模式识别等实现预测、分类及理解人类语言等复杂任务,引领科技创新潮流。
58 0
|
4天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
2天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
3天前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。