《Python算法教程》——第2章 基础知识 2.1 计算领域中一些核心理念-阿里云开发者社区

开发者社区> 异步社区> 正文

《Python算法教程》——第2章 基础知识 2.1 计算领域中一些核心理念

简介:
+关注继续查看

本节书摘来自异步社区《Python算法教程》一书中的第2章,第2.1节,作者[挪威]Magnus Lie Hetland(赫特兰), 凌杰 译,更多章节内容可以访问云栖社区“异步社区”公众号查看。

第2章 基础知识

Tracey:我不知道您在哪里。

Zoe:隐身术就是这样——您应该听说过的。

Tracey:我可不认为这属于基础知识。

——选自《Firefly》第14集台词

在我们将注意力转向本书主体内容,也就是那些数学技术、算法设计原则及经典算法之前,还必须先了解一些最基本的技术与原则。因为当您阅读到后续章节时,至少应该非常清楚类似“无反向环路的加权有向图”以及“Θ(n lg n)运行时间”这些词句所表达的具体含义。同时,我们也理应要对Python中一些基本数据结构的实现方式有个起码的了解。

幸运的是,这些基本问题并非都很难掌握。本章主要将聚焦于两个话题:首先是渐近记法(asymptotic notation),它主要关注的是运行时间的本质。再就是树(tree)与图(graph)这两种数据结构在Python中的实现方式。在这部分内容中,我们将为您介绍一些与程序运行时间有关的实用建议,以及应该如何避免一些基本的设计陷阱。不过,还是先让我们来看看应该如何在特定抽象机制中描述算法的行为吧。

2.1 计算领域中一些核心理念

20世纪30年代中期,英国数学家Alan Turing公开发表了一篇题为《On computable numbers, with an application to the Entscheidungsproblem》(其中译版为《论可计算数及其在判定问题上的应用》)的论文,这篇论文在许多方面都奠定了现代计算机科学的理论基础。如今,由他所提出的抽象设备——图灵机——已经成为了计算领域的理论核心。当然,这在很大程度上是因为该设备本身非常简单,而且容易掌握。图灵机是一种非常简单的抽象设备,它能读、能写,并且能沿着一条无限长的纸带移动。尽管图灵机有着各种不同的具体实现,但每种实现都可以被视为一台有限状态机:它由一个有限的状态集(包括已完成部分)与各种用于触发读写操作及不同状态切换的潜在符号共同组成。我们可以把它们看作这些机器运行所需要的一组规则(例如,“当我们在状态4的情况下遇到X,就向左移动一步,然后写入一个Y,并切换到状态9。”)。尽管这些机器看上去非常简单,但已经很让人惊叹了。因为有了它们,人们在计算领域就几乎无所不能了。

通常来说,所谓算法,实际上指的是一个执行过程,包含了能够解决某个特定问题的有限步骤集(其中可能包含了一些循环和条件元素)。而图灵机则是这个待解决问题的一种正规描述形式。这种形式通常被用于讨论解决该问题所需要的时间(这里既可以指整体时间,也可以指可接受的时间,相关内容将在第11章中详细讨论)。然而对于更细粒度上的算法效率分析来说,图灵机恐怕就不再是我们的首选了,因为这时候相较于可滚动的纸带,我们更需要的是一大块可直接存取的内存。于是随机存取机就应运而生了。

尽管随机存取机这种描述形式使用起来会有点儿复杂,但其实我们只需知道其能力极限在哪里,不至于让它影响我们的算法分析结果就可以了。简而言之,该机器是从标准单处理器计算机简化出来的一种抽象模型,它应该具备以下几个属性。

  • 该机器上不会有任何形式的并发执行,它只有在执行完一条指令后才能执行其他指令。
  • 该机器上的所有标准基本操作,如算术运算、比较运算以及内存存取,所耗费的时间都是常数级的(尽管具体数值上会有所不同),同时它也没有更复杂的基本操作,例如排序。
  • 尽管计算机字(即word,其大小通常等于我们在常数时间内所能读取的值)的字长是有限的,但必须足够大,大到能满足我们在解决问题过程中所有的内存编址的需求,此外还要加上一定比例的额外变量。

当然,在某些情况下,我们可能还会有一些更具体的要求,但就机器本身而言也就大致如此了。

现在,相信我们已经对算法是什么,以及运行它们的抽象硬件环境有了一点直观的认知。下面我们来谈谈整个概念拼图中的最后一块:问题。就我们的目标而言,问题其实指的是输入与输出之间所存在的某种关系。事实上,我们还可以说得更精确一些:这里所反映的是一组集合对之间的关系(数学意义上的)——在这里,对于输入来说,什么样的输出是可接受的——并且借由指定这种关系的过程,我们的问题就会被确定下来。以排序问题为例,我们可以将其视为A、B两个集合之间的关系。这两个集合分别由一组序列组成。除了描述具体的排序过程外(该过程就是算法),我们还需要指定对于一个给定的输入序列(集合A中的某个元素),什么样的输出序列(集合B中元素)是可接受的。我们可以规定结果序列必须由输入序列相同的元素组成,并且将以递增顺序排列(其中的每个元素始终大于或等于前一个元素)。在这里,集合A中的元素(输入序列)就被我们称为问题实例。由此可见,关系本身实际上就是我们的问题。

当然,想要让我们的机器有的放矢,我们还得对其输入进行0、1编码。尽管在这里,我们无须去关心那些编码的具体细节,但是其中的理念很重要,因为其运行时间复杂度(这正是下一节中所要介绍的)是基于知道了问题实例大小,这个大小可以简单看成编码它所需的内存大小。我们会发现,这通常与编码自身的确切属性没有太大关系。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
987 0
数据结构和算法对python意味着什么?
数据结构和算法对于python而言是他的灵魂;程序是数据结构加上算法来实现的,对于任何一门编程语言都离不开数据结构和算法,但是对于python而言内置了基础的数据结构如列表、字典、集合等,再加上众多包,所以弱化了数据结构和算法的使用。
1733 0
Python学习基础知识概要
1.输入输出 输出实例   1 2 print 'hello','world' hello world 输入实例   1 2 3 4 5 name = raw_input(); print "hello,",name   world hello,world
929 0
【Python数据挖掘课程】六.Numpy、Pandas和Matplotlib包基础知识
前面几篇文章采用的案例的方法进行介绍的,这篇文章主要介绍Python常用的扩展包,同时结合数据挖掘相关知识介绍该包具体的用法,主要介绍Numpy、Pandas和Matplotlib三个包。目录: 一.Python常用扩展包 二.Numpy科学计算包
6647 0
NOIP-C++大神培养计划Step1.1.1基础算法——模拟算法1
模拟算法,可以说是最基础的算法了。它的基本定义没太多意思:就是去模拟题目的要求。题意要你怎么做,你就怎么做,看懂了题目,基本上就会做了。 举一个大家耳熟能详的栗子。 A+B Problem给定两个整数A和B,输出他们的和。
1246 0
带你读《Python科学计算(原书第2版)》之三:Python简明教程
本书讲解如何使用Python科学计算软件包来实现和测试复杂的数学算法,第2版针对Jupyter笔记本用户更新了部分代码,并新增了讲解SymPy的章节。书中首先介绍Python相关知识,涵盖IPython、NumPy和SymPy,以及二维和多维图形的绘制。之后讨论不同领域的应用实例,涉及常微分方程、偏微分方程和多重网格,并展示了处理Fortran遗留代码的方法。
526 0
+关注
异步社区
异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区,也是国内领先的IT专业图书社区,致力于优质学习内容的出版和分享,实现了纸书电子书的同步上架,于2015年8月上线运营。公众号【异步图书】,每日赠送异步新书。
12049
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载