算法基础
在开始学习算法之前,您需要了解一些背景知识。首先,你需要知道,简单地说,一个算法是完成某件事的秘诀。它定义了以某种方式执行任务的步骤。
这个定义似乎很简单,但没有人编写算法来执行极其简单的任务。没有人编写如何访问数组中的第四个元素的指令。这里只是假设这是数组定义的一部分,并且您知道如何执行它(如果您知道如何使用所讨论的编程语言)。
通常,人们只针对困难的任务编写算法。算法解释了如何找到复杂代数问题的解决方案,如何在包含数千条街道的网络中找到最短路径,或者如何找到数百种投资的最佳组合以优化利润。
本章解释了一些基本的算法概念,如果你想从算法的学习中获得最大的收获,你应该了解。
可能很容易跳过这一章,直接学习具体的算法,但你至少应该略读一下这些材料。请密切关注“大O符号”一节,因为对运行时性能的良好理解可能意味着算法在秒、小时或根本不执行任务之间的差异。
方法
为了最大限度地利用算法,您必须能够做更多的事情,而不仅仅是遵循它的步骤。您需要了解以下内容:
- 算法的行为它是找到了可能的最佳解决方案,还是只是找到了一个好的解决方案?是否存在多个最佳解决方案?是否有理由选择一个“最佳”解决方案?
- 算法的速度它快吗?慢?对于某些输入,它是否通常很快,但有时很慢?
- 算法的内存需求这个算法需要多少内存?这个数目合理吗?该算法是否需要比计算机可能拥有的(至少在今天)多数十亿tb的内存?
- 算法采用的主要技术您能否重用这些技术来解决类似的问题?
这本书涵盖了所有这些主题。然而,它并没有试图以数学精度覆盖每个算法的每个细节。它使用直观的方法来解释算法及其性能,但没有严格详细地分析性能。尽管这种证明可能很有趣,但它也可能令人困惑并占用大量空间,提供了对大多数程序员来说不必要的细节。毕竟,这本书主要是为需要完成工作的程序员准备的。
本书的章节对相关主题的算法进行了分组。有时主题是他们执行的任务(排序、搜索、网络算法),有时是他们使用的数据结构(链表、数组、哈希表、树),有时是他们使用的技术(递归、决策树、分布式算法)。在高层次上,这些分组似乎是任意的,但当您阅读算法时,您会发现它们是适合在一起的。
除了这些类别之外,许多算法都有跨章节边界的潜在主题。例如,树算法(第10、11和12章)倾向于高度递归(第15章)。链表(第3章)可用于构建数组(第4章)、哈希表(第8章)、堆栈(第5章)和队列(第5章)。引用和指针的思想用于构建链表(第3章)、树(第10、11和12章)和网络(第13和14章)。当你阅读时,注意这些共同的线索。附录A总结了程序用来使这些想法更容易遵循的常用策略。
算法和数据结构
一个算法是执行特定任务的配方。一个数据结构是一种安排数据以使解决特定问题更容易的方法。数据结构可以是一种排列数据的方式数组,一个以某种模式连接项目的链表,一个树,一个图,一个网络,或者更奇特的东西。
算法通常与数据结构密切相关。例如,在第15章“字符串算法”中描述的编辑距离算法使用网络来确定两个字符串有多相似。该算法与网络紧密相连,没有网络就无法工作。相反,算法构建并使用网络,因此如果没有算法,网络就没有用处(甚至没有真正构建)。
算法通常会说:“构建特定的数据结构,然后以特定的方式使用它。”如果没有数据结构,算法就无法存在,如果不打算将数据结构与算法一起使用,那么构建数据结构就没有意义。
伪代码
为了使本书中描述的算法尽可能有用,首先用直观的英语术语描述它们。根据这个高级解释,您应该能够在大多数编程语言中实现该算法。
然而,算法的实现通常包含一些琐碎的细节,这可能会使实现变得困难。为了更容易处理这些细节,许多算法也用伪代码描述。伪代码是一种很像编程语言但不是真正的编程语言的文本。其思想是为您提供在代码中实现算法所需的结构和细节,而不会将算法绑定到特定的编程语言。理想情况下,您可以将伪代码转换为在您的计算机上运行的实际代码。
下面的代码片段显示了一个计算两个整数的最大公约数(GCD)的算法的伪代码示例:
//求a和b的最大公约数// GCD(a, b) = GCD(b, a Mod b)。整数:Gcd(整数:a,整数:b)While (b != 0)//计算余数。整数:余数= a Mod b//计算GCD(b,余数)A = bB =余结束时// GCD(a, 0)是a。返回一个结束肾小球囊性肾病
mod操作符
模算子,写为国防部
在伪代码中,表示除法后的余数。例如,“13国防部
4 "等于1,因为13除以4等于3,余数是1。
陈述“13”国防部
4”通常读作“13 mod 4”或“13 modulo 4”。
伪代码以注释开始。注释以字符开头//
一直延伸到线的末端。
第一行代码是算法的声明。这个算法叫做肾小球囊性肾病
并返回一个整数结果。它接受两个名为一个
而且b
,这两个都是整数。
请注意
执行任务(可选地返回结果)的代码块被不同地调用例程,子例程,方法,程序,子过程,或功能.
声明之后的代码缩进以表明它是方法的一部分。方法主体中的第一行以而
循环。的下面缩进的代码而
语句的条件为而
这个说法仍然成立。
的而
循环以结束时
声明。这个语句并不是严格必要的,因为缩进显示了循环的结束位置,但它提醒了将要结束的语句块的类型。
方法在返回
声明。这个算法返回一个值,所以这个返回
语句指示算法应该返回哪个值。如果算法不返回任何值,例如它的目的是排列值或构建数据结构,则返回
语句后面没有返回值,或者方法可能没有返回值返回
声明。
本例中的代码非常接近实际的编程代码。其他例子可能包含用英语描述的指令或值。在这些情况下,指令用尖括号括起来(<>
),表示你需要把英文指示翻译成程式码。
方法中声明参数或变量时,通常肾小球囊性肾病
算法,这包括参数一个
而且b
还有变量剩余部分
),其数据类型在其前面加上冒号,如整数:剩余
.对于简单的整数循环变量,可以省略数据类型,如对于i = 1到10
.
与某些编程语言不同的另一个特征是伪代码为
循环可以包括一步
语句,指示每次遍历循环后更改循环变量的值。一个为
循环以接下来,我
声明(我
是循环变量)来提醒你哪个循环结束。
例如,考虑以下伪代码:
i = 100 To 0步骤-5//做点什么…接下来,我
这段代码等价于下面的c#代码:
For (int I = 100;I >= 0;I -= 5){//做点什么…}
这两个函数都等价于下面的Python代码:
对于范围为(100,-1,-5)的I:#做点什么……
本书中使用的伪代码使用如果
-然后
-其他的
语句,情况下
语句,以及其他必要的语句。根据您对实际编程语言的了解,这些应该很熟悉。代码需要的任何其他内容都用英语拼写出来。
本书中的许多算法都以返回结果的方法或函数的形式编写。方法的声明从结果的数据类型开始。如果一个方法执行某个任务而不返回结果,那么它就没有数据类型。
下面的伪代码包含两个方法:
//返回输入值的两倍。Integer: DoubleIt(Integer: value)返回2 * value结束DoubleIt//下面的方法做了一些事情,但不返回值。DoSomething(整数:值[])//这里有一些代码。...DoSomething结束
的DoubleIt
方法以整数作为参数并返回一个整数。该代码将输入值加倍并返回结果。
的DoSomething
方法接受一个名为值
.它执行一个任务,但不返回结果。例如,它可以对数组中的项进行随机或排序。(请注意,本书假设数组以索引0开始。例如,包含三个项的数组的索引为0、1和2。)
伪代码应该是直观的,容易理解的,但是如果你发现一些对你来说没有意义的东西,请随时在本书的讨论论坛上提出问题www.wiley.com/go/essentialalgorithms
或电邮至RodStephens@CSharpHelper.com
.我会给你指正确的方向。
伪代码的一个问题是它没有编译器来检测错误。作为对基本算法的检查,并提供一些实际代码供参考,许多算法和练习的c#和Python实现可在本书的网站上下载。
算法的特性
一个好的算法必须具备三个特征:正确性、可维护性和效率。
显然,如果一个算法不能解决它所设计的问题,它就没有多大用处。如果它不能给出正确答案,那么使用它就没有什么意义了。
请注意
有趣的是,一些算法只在某些时候产生正确答案,但仍然有用。例如,一个算法可能能够以一定的概率给你一些信息。在这种情况下,您可以多次重新运行算法,以增加您对答案正确的信心。在第二章“数值算法”中描述的费马素数检验就是这种算法。
如果一个算法不可维护,那么在程序中使用它是危险的。如果一个算法简单、直观且优雅,那么您可以确信它产生了正确的结果,如果结果不正确,您也可以修正它。如果算法是复杂的、令人困惑的、令人费解的,那么您在实现它时可能会遇到很多麻烦,如果出现错误,修复它将更加困难。如果很难理解,你怎么知道它是否产生了正确的结果?
请注意
这并不意味着不值得研究令人困惑和困难的算法。即使您在实现算法时遇到了困难,您也可以在尝试中学到很多东西。随着时间的推移,你的算法直觉和技能会提高,所以你曾经认为令人困惑的算法似乎会更容易处理。但是,您必须始终彻底测试所有算法,以确保它们产生正确的结果。
大多数开发人员在效率上花费了大量精力,而效率当然很重要。如果一个算法产生了正确的结果,并且易于实现和调试,那么如果它需要七年才能完成,或者它需要的内存超过计算机可能容纳的容量,那么它仍然没有多大用处。
为了研究算法的性能,计算机科学家会研究算法的性能如何随着问题大小的变化而变化。如果您将算法正在处理的值的数量增加一倍,那么运行时间是否会增加一倍?它会增加4倍吗?它是否会呈指数增长,以至于突然需要数年才能完成?
您可以询问关于内存使用或算法所需的任何其他资源的相同问题。如果您将问题的大小增加一倍,那么所需的内存量是否也会增加一倍?
您还可以就算法在不同情况下的性能提出相同的问题。算法在最坏情况下的表现是什么?最坏的情况发生的可能性有多大?如果你在一个大的随机数据集上运行算法,它的平均情况性能如何?
为了了解问题大小与性能之间的关系,计算机科学家使用大O符号,这将在下一节中进行描述。
大O符号
大O符号使用一个函数来描述当问题规模变得非常大时,算法的最差情况性能与问题规模的关系。(这有时被称为程序的渐近性能)。函数写在大写字母后面的圆括号内O.
例如,这意味着一个算法的运行时间(或者内存使用情况或者你测量的任何东西)会随着输入数量n的平方而增加。如果你把输入数量增加一倍,运行时间会增加大约4倍。类似地,如果输入数量增加三倍,运行时间将增加9倍。
请注意
经常O (N2)发音为“o (N²)”。例如,你可能会说,“在第6章“排序”中描述的快速排序算法,最坏情况下的性能为o (N²)。”
计算算法的大O符号有五个基本规则。
- 如果一个算法执行特定的步骤序列乘以一个数学函数f,那么它需要步骤。
- 如果算法执行的操作为步骤,然后执行第二个操作函数f和g的步长,则算法的总性能为.
- 如果一个算法时间和函数大于对于较大的N,则算法的性能可简化为.
- 如果算法执行的操作为步骤,对于该操作中的每一步,它都会执行另一个步骤步长,则该算法的总性能为.
- 忽略常数倍数。如果C是常数,和,和.
这些规则可能看起来有点正式,因为大家都在谈论而且,但它们相当容易应用。如果它们看起来令人困惑,一些例子应该会让它们更容易理解。
规则1
如果一个算法执行特定的步骤序列乘以一个数学函数f,然后这需要步骤。
考虑以下用伪代码编写的算法,用于查找数组中最大的整数:
Integer: findmaximum (Integer: array[])整数:large = array[0]对于i = 1到<最大索引>If(数组[i] >最大)那么最大=数组[i]接下来,我最大回报结束FindLargest
的FindLargest
算法以一个整数数组作为参数,并返回一个整数结果。它从设置变量开始最大
等于数组中的第一个值。
然后循环遍历数组中的其余值,将每个值与最大
.如果它找到的值大于最大
,程序设置最大
等于这个值。
在它完成循环之后,算法返回最大
.
这个算法检查了数组中N个元素中的每一个,所以它已经检查了的性能。
请注意
通常算法大部分时间都花在循环中。一个算法不可能用固定数量的代码行执行超过几个步骤,除非它包含某种类型的循环。
研究一个算法的循环,计算出它需要多少时间。
规则2
如果算法执行的操作为步骤,然后执行第二个操作函数f和g的步骤,然后该算法的总性能为.
如果你再看一下FindLargest
在前一节中所示的算法中,您将看到有几个步骤实际上不在循环中。下面的伪代码显示了相同的步骤,它们的运行时顺序显示在注释的右边:
Integer: findmaximum (Integer: array[])Integer: large = array[0] // O(1)对于i = 1到<最大索引> // O(N)If(数组[i] >最大)那么最大=数组[i]接下来,我返回最大// O(1)结束FindLargest
该算法在进入循环之前执行一个设置步骤,然后在循环结束后再执行一个步骤。这两个步骤的性能都是O(1)(它们每个都只是一个步骤),所以算法的总运行时间实际上是.你可以用普通代数把这些项组合起来写成.
规则3
如果一个算法时间和函数大于对于大N,然后该算法的性能可以简化为.
前面的示例表明FindLargest
算法有运行时间.当N变大时,函数N大于常数值2,所以化简为.
当问题规模变得非常大时,忽略较小的函数可以让你专注于算法的渐近行为。它还允许您忽略相对较小的设置和清理任务。如果一个算法花了一些时间构建简单的数据结构,或者为执行大型计算做准备,那么只要设置时间相对于主要计算的长度较小,您就可以忽略它。
规则4
如果算法执行的操作为步骤,对于该操作中的每一步,它都会执行另一个步骤步骤,然后该算法的总性能为.
考虑以下确定数组是否包含重复项的算法。(请注意,这不是检测重复的最有效方法。)
Boolean: containsduplicate (Integer: array[])//遍历数组的所有项。对于i = 0到<最大索引>对于j = 0到<最大索引>//查看这两个项目是否重复。If (i != j)则If (array[i] == array[j])则返回True如果下一个我接下来,我//如果我们到达这一点,就没有重复项。返回假结束ContainsDuplicates
该算法包含两个嵌套循环。外层循环遍历数组的所有N个元素,所以它取步骤。
对于每次通过外部循环,内部循环也迭代数组中的N个项,因此它也需要步骤。
由于一个循环嵌套在另一个循环中,因此组合性能为.
规则5
忽略常数倍数。如果C是常数,和,和.
如果你再看一下ContainsDuplicates
算法,您将看到内部循环实际上执行一个或两个步骤。它执行一个如果
测试这些指标我
而且j
都是一样的。如果它们不同,就进行比较数组(我)
而且array [j]
.它也可以返回值真正的
.
如果忽略了额外的步骤返回
语句(它最多只发生一次),并假设算法同时执行如果
语句(正如它在大多数时候所做的那样),然后内部循环接受步骤。因此,该算法的总性能为.
规则5允许您忽略因子2,因此运行时间为.
这条规则实际上可以追溯到大O符号的目的。这个想法是为了感受N增加时算法的行为。在这种情况下,假设你将N增加2倍。
如果你代入这个值进入等式,得到如下结果:
这是原值的四倍,因此运行时间增加了4倍。
现在尝试用规则5简化的运行时做同样的事情.堵塞在这个方程中有:
这是原值的四倍,所以这也意味着运行时间增加了4倍。
是否使用公式或者只是,结果是一样的:问题的大小增加2倍,运行时间增加4倍。这里重要的不是常数;而是运行时间随着输入数量N的平方而增加。
请注意
重要的是要记住,大O符号只是为了让您了解算法的理论行为。你在实践中的结果可能会有所不同。例如,假设一个算法的性能是O(N),但如果你不忽略常数,实际执行的步数是100,000,000 + N,除非N真的很大,否则你可能无法安全地忽略常数。
常见运行时函数
在研究算法的运行时时,经常会出现一些函数。下面几节给出了一些最常见函数的示例。它们也给了你一些观点,这样你就会知道,例如,一个算法是否性能合理。
1
不管问题有多大,具有O(1)性能的算法所花费的时间都是常数。这类算法倾向于执行相对琐碎的任务,因为它们甚至不能在O(1)时间内查看所有输入。
例如,在某一时刻快速排序
算法需要在值数组中选择一个数字。理想情况下,该数字应该位于数组中所有值的中间位置,但没有简单的方法来判断哪个数字可能恰好位于中间。(例如,如果数字平均分布在1和100之间,50将是一个很好的除数。)下面的算法展示了解决这个问题的一种常见方法:
Integer: DividingPoint(Integer: array[])整数:number1 = array[0]Integer: number2 = array[<数组>的最后一个索引]Integer: number3 = array[<数组> / 2的最后一个索引]如果()则返回number1 如果()则返回number2 返回number3结束MiddleValue
该算法选择数组的开始、结束和中间的值;比较;并返回位于其他两项之间的项。这可能不是从整个数组中选出的最好的项目,但有一个很好的机会,它不是一个太糟糕的选择。
因为这个算法只执行几个固定的步骤,所以它的性能是O(1),并且它的运行时间与输入的数量n无关(当然,这个算法并不是真正独立的。这只是一个更复杂算法的一小部分。)
o (Log N)
一种算法性能通常在每一步都将必须考虑的项目数量除以一个固定的分数。
例如,图1.1显示了一个已排序的完全二叉树。这是一个二叉树因为每个节点最多有两个分支。这是一个完整的树因为每一层(可能除了最后一层)都是完全满的,最后一层中的所有节点都被分组在左侧。这是一个分类树因为每个节点的值至少和它的左子节点一样大,不大于它的右子节点。(第十章“树”有很多关于树的内容。)
图1.1:搜索一个完整的二叉树需要O(log N)步。
对数
某对数底数的对数是为了得到某一结果所必须取的底数的幂。例如,log2(8)是3,因为23.= 8。这里,2是对数底。
通常在算法中,基数是2,因为输入被重复地分为两组。正如您将很快看到的,对数底数在大O符号中并不重要,因此通常省略它。
下面的伪代码展示了在图1.1所示的树中搜索特定项目的一种方法:
节点:FindItem(Integer: target_value)节点:test_node = <树>的根做的永远//如果我们从树上掉下来。该值不存在。If (test_node == null)则返回nullIf (target_value == test_node.Value// test_node保存目标值。//这是我们需要的节点。返回test_nodeElse If (target_value < test_node.Value//移动到左边的子元素。Test_node = Test_node。LeftChild其他的//移动到右边的子元素。Test_node = Test_node。RightChild如果最后做结束FindItem
第10章“树”详细介绍了树算法,但是您应该能够从下面的讨论中获得算法的要点。
算法声明并初始化变量test_node
所以它指向树顶部的根结点。(传统上,计算机程序中的树都是根在顶部,不像真正的树。)然后进入一个无限循环。
如果test_node
是零
,则目标值不在树中,因此算法返回零
.
请注意
的值
零
是一个特殊值,您可以将其赋给通常应指向对象(如树中的节点)的变量。的值零
意思是“这个变量不指向任何东西。”
如果test_node
那么,保持目标值test_node
是你正在寻找的节点,所以算法会返回它。
如果target_value
是小于值在吗test_node
,则算法集test_node
等于它的左子结点。(如果test_node
在树的底部,它的LeftChild
值是零
,算法在下次进行循环时处理这种情况。)
如果test_node
的值不等于target_value
并且不小于target_value
,那么它一定大于target_value
.在这种情况下,算法集合test_node
等于它的右子结点。(再一次,如果test_node
在树的底部,它的RightChild
是零
,算法在下次进行循环时处理这种情况。)
的变量test_node
沿着树向下移动,最终要么找到目标值,要么从树上掉下来test_node
是零
.
要理解这种算法的性能,问题就变成了在树下走多远test_node
必须在它找到之前离开target_value
或者从树上掉下来。
有时算法很幸运,能马上找到目标值。如果图1.1中的目标值为7,则算法一步就能找到并停止。即使目标值不在根节点上(例如,如果目标值是4),程序在停止之前可能只需要检查树的一小部分。
然而,在最坏的情况下,算法需要从上到下搜索树。
事实上,树中大约有一半的节点是底部缺少子节点的节点。如果这棵树是一棵完整的树,每个节点都有0到2个子节点,那么最底层将刚好包含树的一半节点。这意味着如果你在树中搜索随机选择的值,算法将不得不在大多数时候遍历树的大部分高度。
现在的问题是,“这棵树有多高?”高度为H的完全二叉树节点。从另一个方向来看,包含N个节点的完整完整二叉树具有高度.因为算法在最坏(和平均)的情况下从上到下搜索树,因为树的高度大约为,算法运行时间。
在这一点上,对数的一个奇怪的特征开始发挥作用。你可以用下面的公式将对数从以a为底转换为以B为底:
设置,可以使用此公式转换值换成任意以A为底的对数
的值对于任何给定的a都是常数,大O符号忽略了常数倍数,这意味着和对于任何log以a为底的日志,这个运行时通常是这样写的没有表示基底(也没有括号使它看起来不那么杂乱)。
这个算法是很多算法中的典型的性能。在每一步中,它将必须考虑的项目数量分为两个大小大致相等的组。
因为对数基数在大O符号中无关紧要,所以算法使用哪个分数来划分它所考虑的项并不重要。这个示例在每一步中都将项的数量分成两半,这在许多对数算法中是常见的。但它仍然存在如果它将剩余的项目除以1/10的因子,并且在每一步都取得了很大的进展,或者如果它将项目除以9/10的因子,并且取得了相对较小的进展,则表现为。
对数函数随着N的增加,增长相对缓慢,所以算法性能通常足够快,因此非常有用。
√6 N
有些算法性能(其中SQRT是平方根函数),但它们并不常见,本书也没有涉及它们。这个函数的增长非常缓慢,但比.
N
的FindLargest
在前一节“规则1”中描述的算法具有的性能。有关为什么会这样的解释,请参阅那一节的性能。
函数N的增长速度比而且但仍然不是很快,所以大多数算法表演在实践中表现得很好。
N log N
假设一个算法循环遍历习题集中的所有项目,然后,对于每个循环,执行某种计算该项目。在这种情况下,算法已经或的性能。
或者,一种算法可以执行某种操作,对于其中的每一步,对问题中的每一项都做一些操作。
例如,假设您已经构建了一个已排序的树,其中包含前面描述的N个项目。你还有一个包含N个值的数组,你想知道数组中的哪些值也在树中。
一种方法是循环遍历数组中的值。对于每个值,都可以使用前面描述的方法在树中搜索该值。算法检查N个项目,并对每个项目执行步骤,所以总的运行时间是.
许多通过相互比较项来工作的排序算法都有一个运行时。事实上,可以证明,任何通过比较项目进行排序的算法都必须使用至少步骤,所以这是你能做的最好的,至少在大O符号中。其中一些算法仍然比其他算法快,因为大O符号忽略了常数。一些不使用比较的算法可以更快地排序。第6章更多地讨论了各种运行时的算法。
N2
一个循环遍历所有输入的算法然后对于每个输入循环遍历输入的性能。例如,ContainsDuplicates
在“规则4”一节中描述的算法开始运行时间。有关算法的描述和分析,请参阅该部分。
N的其他幂,比如而且,是可能的,而且明显比.
一种算法被称为多项式运行时间如果它的运行时间涉及到N的任何多项式。,,,甚至都是多项式运行时间。
多项式运行时间很重要,因为在某种意义上,这些问题仍然可以解决。下面描述的指数和阶乘运行时间增长非常快,所以具有这些运行时间的算法只适用于非常少量的输入。
指数函数如增长非常快,所以它们只适用于小问题。具有这些运行时的算法通常会寻找输入的最佳选择。
例如,在背包问题,你会得到一组对象,每个对象都有一个权重和一个值。你还有一个可以承受一定重量的背包。你可以在背包里放一些重的东西,也可以放很多轻的东西。挑战在于选择最适合背包的总价值最大的物品。
这似乎是一个简单的问题,但唯一已知的寻找最佳可能解决方案的算法本质上要求您检查所有可能的项目组合。
要想知道有多少种可能的组合,请注意每个物品要么在背包里,要么在背包外,所以每个物品有两种可能。如果你把这些项目的可能性相乘,你会得到所有可能的选择。
有时候,你不需要尝试所有可能的组合。例如,如果添加第一个项目将完全填满背包,则不需要添加包括第一个项目和另一个项目的任何选择。但是,一般来说,您不能排除足够多的可能性来显著缩小搜索范围。
对于具有指数级运行时间的问题,您经常需要使用启发式-通常会产生良好结果,但你不能保证会产生最佳结果的算法。
N !
的阶乘函数,写成N!发音为“N !”,用于大于0的整数.这个函数增长得比指数函数快得多.通常,具有阶乘运行时的算法寻找输入的最佳安排。
例如,在旅行推销员问题(TSP),你会得到一个城市列表。我们的目标是找到一条路线,该路线只访问每个城市一次,并返回起点,同时最大限度地减少总路程。
这对于少数城市来说并不难,但对于许多城市来说,这个问题就变得具有挑战性了。最明显的方法是尝试各种可能的城市安排。按照这个算法,你可以为第一个城市选择N个可能的城市。在做出选择之后,你有接下来可能去的城市。然后是可能是第三个城市,等等,所以安排的总数是.
可视化功能
表1.1显示了前几节中描述的运行时函数的一些值,以便您可以看到这些函数的增长速度。
表1.1:不同输入的函数值
N | log2 (N) | sqrt (N) | N | N2 | 2 n | N ! |
1 | 0.00 | 1.00 | 1 | 1.00 | 2 | 1 |
5 | 2.32 | 2.23 | 5 | 25 | 32 | 625年 |
10 | 3.32 | 3.16 | 10 | One hundred. | 1024年 | |
15 | 3.90 | 3.87 | 15 | 225年 | ||
20. | 4.32 | 4.47 | 20. | 400年 | ||
50 | 5.64 | 7.07 | 50 | 2500年 | ||
One hundred. | 6.64 | 10.00 | One hundred. | |||
1000 | 9.96 | 31.62 | 1000年 | - - - - - - | ||
10000 | 13.28 | 100.00 | - - - - - - | - - - - - - | ||
100000 | 16.60 | 316.22 | - - - - - - | - - - - - - |
图1.2显示了这些函数的图形。一些函数已经被缩放,以便它们更适合于图形,但您可以很容易地看到当x变大时,哪个函数增长最快。即使除以100也不能让阶乘函数在图上保持很长时间。
图1.2:对数函数、平方根函数、线性函数甚至多项式函数都以合理的速度增长,但指数函数和阶乘函数增长得非常快。
实际考虑
尽管理论行为对于理解算法的运行时行为很重要,但由于几个原因,实际考虑因素在实际性能中也发挥着重要作用。
对算法的分析通常认为所有步骤所花费的时间相同,即使情况可能并非如此。例如,创建和销毁新对象可能比将整数值从数组的一部分移动到另一部分花费的时间长得多。在这种情况下,使用数组的算法可能优于使用大量对象的算法,即使第二个算法在大O表示法中表现更好。
许多编程环境还提供对操作系统功能的访问,这些功能比基本算法技术更有效。例如,部分insertionsort
算法要求您将数组中的一些项向下移动一个位置,以便您可以在它们之前插入一个新项。这是一个相当缓慢的过程,对算法有很大的贡献的性能。然而,许多程序可以使用函数(例如RtlMoveMemory
在。net程序中MoveMemory
在Windows c++程序中),可以一次性移动内存块。程序不需要遍历数组,每次移动一个项,而是可以调用这些函数一次移动整个数组值集,从而使程序运行得更快。
仅仅因为算法具有一定的理论渐近性能并不意味着您不能利用编程环境提供的任何工具来提高性能。一些编程环境还提供了一些工具,这些工具可以执行与本书中描述的某些算法相同的任务。例如,许多库都包含排序例程,可以很好地对数组进行排序。微软的。net框架,被c#和Visual Basic使用,包括一个数组中。排序
方法,该方法使用的实现使用您自己的代码不太可能击败它——至少在一般情况下是这样。类似地,Python列表有一个排序
方法对列表中的项进行排序。
对于特定的问题,如果您有关于数据的额外信息,有时仍然可以击败内置排序方法。(例如,阅读countingsort
第六章。)
还可以使用特殊用途的库来帮助您完成某些任务。例如,您可以使用网络分析库,而不是编写自己的网络工具。类似地,数据库工具可以为您节省大量构建树和排序的工作。构建自己的平衡树可能会获得更好的性能,但使用数据库会减少很多工作。
如果您的编程工具包含执行其中一种算法任务的函数,请务必使用它们。您可能会获得比自己更好的性能,而且要做的调试肯定会更少。
最后,对于非常大的问题,最好的算法并不总是最快的。如果你要对一大堆数字排序,快速排序
通常提供良好的性能。如果你只对三个数字排序,一个简单的数列如果
语句可能会提供更好的性能,并且会简单得多。即使快速排序
是否有更好的性能,程序在1毫秒还是2毫秒内完成排序有关系吗?除非您计划执行多次排序,否则最好使用更容易调试和维护的简单算法,而不是节省1毫秒的复杂算法。
如果您使用前面段落中描述的库,您可能不需要自己编写所有这些算法,但了解这些算法是如何工作的仍然是有用的。如果您了解算法,即使不编写算法,也可以更好地利用实现算法的工具。例如,如果您知道关系数据库通常使用b -树(和类似的树)来存储它们的索引,那么您就会更好地理解预分配和填充因子的重要性。如果你明白的话快速排序
,你就会知道为什么有些人认为。net框架是数组中。排序
方法不是加密安全的。(这将在第6章的“使用快速排序”一节中讨论。)
理解这些算法还可以让您将它们应用于其他情况。你可能不需要使用归并排序
,但是您可以使用它的分治方法来解决多个处理器上的其他问题。
总结
为了最大限度地利用算法,您不仅需要了解它是如何工作的,还需要了解它的性能特征。本章解释了大O符号,你可以用它来研究算法的性能。如果你知道一个算法的大O运行时行为,你可以估计如果你改变问题的大小,运行时将会改变多少。
本章还描述了一些导致常见运行时函数的算法情况。图1.2显示了这些方程的图形,以便您可以感受到随着问题规模的增加,每个方程的增长速度有多快。根据经验,在多项式时间内运行的算法通常足够快,您可以在中等大的问题上运行它们。然而,随着问题规模的增加,具有指数或阶乘的算法运行时间增长得非常快,因此只能在相对较小的问题规模上运行它们。
现在您已经对如何分析算法速度有了一定的了解,接下来就可以学习一些特定的算法了。下一章讨论数值算法。它们往往不需要复杂的数据结构,所以它们通常非常快。
练习
你可以在附录b中找到这些练习的答案。星号表示特别难的问题。
- “规则4”部分描述了一个
ContainsDuplicates
有运行时间的算法.考虑以下算法的改进版本:Boolean: containsduplicate (Integer: array[])//循环数组中除了最后一个元素以外的所有元素。对于i = 0到<最大索引> - 1//遍历item i后面的item。对于j = i + 1到<最大索引>//查看这两个项目是否重复。If (array[i] == array[j])则返回True下一个我接下来,我//如果我们到达这一点,就没有重复项。返回假结束ContainsDuplicates
这个新版本的运行时间是多少?
- 表1.1显示了问题大小N与各种运行时函数之间的关系。研究这种关系的另一种方法是研究具有一定速度的计算机在给定时间内可以执行的最大问题规模。
例如,假设一台计算机每秒可以执行一百万步算法。考虑一个运行的算法时间。在一个小时内,计算机可以解决一个问题(因为这是计算机在一小时内可以执行的步数)。
制作一个表,显示这台计算机在一秒、一分钟、一小时、一天、一周和一年内可以执行表1.1中列出的每个函数的最大问题大小N。
- 有时,在大O符号中忽略的常数很重要。例如,假设有两个算法可以做相同的工作。第一个要求步骤,另一个要求步骤。对于N的多少,你会选择哪种算法?
- *假设您有两个算法,其中一个使用步骤,和一个使用步骤。对于N的多少,你会选择哪种算法?
- 假设一个程序以N个字母作为输入,并生成所有可能的无序字母对。例如,对于输入ABCD,程序生成组合AB、AC、AD、BC、BD和CD。(这里无序意味着AB和BA被视为同一对)。算法的运行时间是多少?
- 假设一个有N个输入的算法为一个平面上的每个单位正方形生成值多维数据集。算法的运行时间是多少?
- 假设一个有N个输入的算法为一个的边缘上的每个单位立方体生成值如图1.3所示。算法的运行时间是多少?图1.3:该算法为多维数据集的“骨架”上的多维数据集生成值。
- *假设您有一个算法,对于N个输入,为图1.4所示形状中的每个小立方体生成一个值。假设存在明显的隐藏立方体,因此图中的形状不是空心的,那么算法的运行时间是多少?图1.4:随着N的增加,该算法将形状增加一层。
- 你能有一个没有数据结构的算法吗?你能有一个没有算法的数据结构吗?
- 考虑以下两种粉刷栅栏的算法:
Algorithm1 ()对于i = 0到<栅栏> - 1中的板数<油漆板编号i>接下来,我结束Algorithm1Algorithm2(Integer: first_board, Integer: last_board)If (first_board == last_board) Then//只有一个板子。只要把它涂上。<油漆板编号first_board> . <油漆板编号first_board> .其他的// There's more one board. // There's more one board.把黑板分开//分成两组并递归地绘制它们。整数:middle_board = (first_board + last_board) / 2Algorithm2 (first_board middle_board)Algorithm2(middle_board + 1, last_board)如果结束Algorithm2
这两个算法的运行时间是多少,其中N是栅栏里的板子数?哪种算法更好?
- *你可以通过以下规则递归地定义斐波那契数:
斐波那契(0)= 1斐波那契(1)= 1斐波那契(n) =斐波那契(n - 1) +斐波那契(n - 2)
斐波那契数列从1、1、2、3、5、8、13、21、34、55、89开始。
斐波那契函数与图1.2所示的运行时函数相比如何?