Python实现一些算法和数据结构

引言

在科学领域中（物理学、生命科学和社会科学），为了验证一个关于数据集的假设是否合理，程序员经常先快速地编码实现一个简单的算法，然后使用少量数据运行该算法。如果结果令人鼓舞，那么接下来就要开发可以运行（可能要一次又一次地运行）在大规模数据集上的程序实现，艰苦的工作就开始了，这种实现要在高效算法的基础上才能完成。

高效算法的实现非常困难，对于那些成功的专业计算机科学家来说，整个职业生涯中可能只会开发出一种算法。多数人永远都不会开发新的算法，我们要做的是，学会在面对问题时将复杂性减到最小，并将它们转换为以前已经解决了的问题。

更具体地说，我们需要：

1.理解问题的内在复杂度

2.思考如何将问题分解为多个子问题

3.将这些子问题与已经有高效算法的其他问题联系起来

本节我们将会介绍一些示例，目的是为了让我们在算法设计方面具有一些直觉性知识。

请记住，你并不总是需要选择最有效率的算法，一个在各方面都最有效率的程序经常是难以理解的，我们也没必要去理解，一般而言，比较好的策略是先用最简单直接的方式解决手头上的问题，再仔细测试找出计算上的瓶颈，然后仔细研究造成瓶颈的那部分程序，并找出改善计算复杂度的方法。

搜索算法

搜索算法就是在一个项目集合中找出一个或一组具有某种特点的项目，我们将项目集合称为搜索空间。它可以很具体，比如一组电子病历；也可以很抽象，比如所有整数的集合。在实际工作中，大量问题都可以转化为搜索问题。

我们将研究两种搜索列表的算法，每种方法都满足以下规范：

也许有人会问，这个函数在语义上不是和Python表达式e in L完全一样吗？没错，其实也就是这样的。如果我们不关心判断“e是否在L中”时的效率问题，那么我们只需要简单地使用这个表达式即可。

线性搜索与间接引用元素

Python使用以下算法确定列表中是否有某个元素：

如果元素e不在列表中，那么算法就会执行O(len(L))次测试。也就是说，复杂度至多与L的长度成线性关系。为什么是“至多”成线性关系呢？只有当循环中的每个操作都可以在常数时间内完成时，才是线性关系。这就引发了一个问题：python能否在常数时间内提取列表中的第i个元素？因为我们的计算模型假设取出一个内存地址中的内容是一个常数时间操作，所以问题就变成能否在常数时间内计算出列表中第i个元素的地址。

首先考虑简单情形。假设列表中每个元素都是整数，这意味着列表中每个元素的大小都相同，如4个内存单位（4个8位字节）。假设列表中的元素是连续存储的，那么列表中的第i个元素的内存地址就是start + 4*i，这里的start是列表起始位置的地址。因此，我们可以认为，Python能够在常数时间内计算出整数列表中第i个元素的地址。

当然，我们知道Python列表其实可以包含非int类型对象，而且同一个列表中对象的大小和类型也可以都不同。你可能会认为这是一个问题，但实际上并不是。

在Python中，列表其实被表示成一个长度（列表中对象的数量）和一个固定长度的对象指针序列。因此基本的操作和上面其实是一致的。访问操作也可以在常数时间内完成。

这个例子展示了计算中最重要的实现技术之一：间接引用。一般来说，间接引用就是，要访问目标元素时，先访问另一个元素，再通过包含在这个元素中的引用来访问目标元素。我们每次使用变量引用与变量绑定的对象时，就是这么做的。当我们使用一个变量访问列表并使用保存在列表中的引用访问另一个对象时，实际上用了双重间接引用。