环保网站模板代码,公众号1000粉丝月收入,自己做民宿在什么网站上投放,做情侣网站算法是解决特定问题求解步骤的描述#xff0c;在计算机中表现为指令的有限序列#xff0c;并且每条指令表示一个或多个操作。
1. 两种算法的比较
大家都已经学过一门计算机语言#xff0c;不管学的是哪一种#xff0c;学得好不好#xff0c;好歹是可以写点小程序了。现在…算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列并且每条指令表示一个或多个操作。
1. 两种算法的比较
大家都已经学过一门计算机语言不管学的是哪一种学得好不好好歹是可以写点小程序了。现在我要求你写一个求123……100结果的程序你应该怎么写呢
大多数人会马上写出下面的C语言代码或者其他语言的代码 这是最简单的计算机程序之一它就是一种算法我不去解释这代码的含义了。问题在于你的第一直觉是这样写的但这样是不是真的很好是不是最高效
此时我不得不把伟大数学家高斯的童年故事拿来说一遍也许你们都早已经听过但不妨再感受一下天才当年是如何展现天分和才华的。
据说18世纪生于德国小村庄的高斯上小学的一天课堂很乱就像我们现在下面那些窃窃私语或者拿着手机不停摆弄的同学一样老师非常生气后果自然也很严重。于是老师在放学时就要求每个学生都计算12…100的结果谁先算出来谁先回家。天才当然不会被这样的问题难倒高斯很快就得出了答案是5050。
老师非常惊讶因为他自己想必也是通过1233366410……49501005050这样算出来的也算了很久很久。说不定为了怕错还算了两三遍。可眼前这个少年为何可以这么快地得出结果
高斯解释道 用程序来实现如下 神童就是神童他用的方法相当于另一种求等差数列的算法不仅仅可以用于1加到100就是加到一千、一万、一亿需要更改整型变量类型为长整型否则会溢出也就是瞬间之事。但如果用刚才的程序显然计算机要循环一千、一万、一亿次的加法运算。人脑比电脑算得快似乎成为了现实。 2. 算法定义
算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列并且每条指令表示一个或多个操作。
刚才的例子我们也看到对于给定的问题是可以有多种算法来解决的。算法定义中提到了指令指令能被人或机器等计算装置执行。它可以是计算机指令也可以是我们平时的语言文字。为了解决某个或某类问题需要把指令表示成一定的操作序列操作序列包括一组操作每一个操作都完成特定的功能这就是算法了。
3. 算法的特性
算法具有五个基本特性输入、输出、有穷性、确定性和可行性。
3.1 输入输出
输入和输出特性比较容易理解算法具有零个或多个输入。尽管对于绝大多数算法来说输入参数都是必要的但对于个别情况如打印“hello world”这样的代码不需要任何输入参数因此算法的输入可以是零个。算法至少有一个或多个输出算法是一定需要输出的不需要输出你用这个算法干吗输出的形式可以是打印输出也可以是返回一个或多个值等。
3.2 有穷性
有穷性指算法在执行有限的步骤之后自动结束而不会出现无限循环并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的而是在实际应用当中合理的、可以接受的“有边界”。你说你写一个算法计算机需要算上个二十年一定会结束它在数学意义上是有穷了可是媳妇都熬成婆了算法的意义也不就大了。
3.3 确定性
确定性算法的每一步骤都具有确定的含义不会出现二义性。 算法在一定条件下只有一条执行路径相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。
3.4 可行性
可行性算法的每一步都必须是可行的也就是说每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法不是说理论上不能实现而是因为过于复杂我们当前的编程方法、工具和大脑限制了这个工作不过这都是理论研究领域的问题不属于我们现在要考虑的范围。 4. 算法设计的要求
4.1正确性
算法的“正确”通常分为以下四个层次。
1算法程序没有语法错误。
2算法程序对于合法的输入数据能够产生满足要求的输出结果。
3算法程序对于非法的输入数据能够得出满足规格说明的结果。
4算法程序对于精心选择的甚至刁难的测试数据都有满足要求的输出结果。
对于这四层含义层次1要求最低但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱不能算是生活幸福一样。而层次4是最困难的我们几乎不可能逐一验证所有的输入都得到正确的结果。因此算法的正确性在大部分情况下都不可能用程序来证明而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的代价非常昂贵。所以一般情况下我们把层次3作为一个算法是否正确的标准。 4.2 可读性
可读性算法设计的另一目的是为了便于阅读、理解和交流。
可读性高有助于人们理解算法晦涩难懂的算法往往隐含错误不易被发现并且难于调试和修改。
我们写代码的目的一方面是为了让计算机执行但还有一个重要的目的是为了便于他人阅读让人理解和交流自己将来也可能阅读如果可读性不好时间长了自己都不知道写了些什么。可读性是算法也包括实现它的代码好坏很重要的标志。 4.3 健壮性
一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。
健壮性当输入数据不合法时算法也能做出相关处理而不是产生异常或莫名其妙的结果。
4.4 时间效率高和存储量低
时间效率指的是算法的执行时间对于同一个问题如果有多个算法能够解决执行时间短的算法效率高执行时间长的效率低。
存储量需求指的是算法在执行过程中需要的最大存储空间主要指算法程序运行时所占用的内存或外部硬盘存储空间。
设计算法应该尽量满足时间效率高和存储量低的需求。 5. 算法效率的度量方法
5.1 事后统计方法
事后统计方法这种方法主要是通过设计好的测试程序和数据利用计算机计时器对不同算法编制的程序的运行时间进行比较从而确定算法效率的高低。
但这种方法显然是有很大缺陷的
■ 必须依据算法事先编制好程序这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法不是竹篮打水一场空吗
■ 时间的比较依赖计算机硬件和软件等环境因素有时会掩盖算法本身的优劣。要知道现在的一台四核处理器的计算机跟当年286、386、486等老爷爷辈的机器相比在处理算法的运算速度上是不能相提并论的而所用的操作系统、编译器、运行框架等软件的不同也可以影响它们的结果就算是同一台机器CPU使用率和内存占用情况不一样也会造成细微的差异。
■ 算法的测试数据设计困难并且程序的运行时间往往还与测试数据的规模有很大关系效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序不管用什么算法差异几乎是零。而如果有一百万个随机数字排序那不同算法的差异就非常大了。那么我们为了比较算法到底用多少数据来测试这是很难判断的问题。
基于事后统计方法有这样那样的缺陷我们考虑不予采纳。 5.2 事前分析估算方法
我们的计算机前辈们为了对算法的评判更科学研究出了一种叫做事前分析估算的方法。
事前分析估算方法在计算机程序编制前依据统计方法对算法进行估算。
经过分析我们发现一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素
1算法采用的策略、方法。
2编译产生的代码质量。
3问题的输入规模。
4机器执行指令的速度。
第1条当然是算法好坏的根本第2条要由软件来支持第4条要看硬件性能。也就是说抛开这些与计算机硬件、软件有关的因素一个程序的运行时间依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。
我们来看看今天刚上课时举的例子两种求和的算法 显然第一种算法执行了1n1n1次2n3次而第二种算法是1113次。事实上两个算法的第一条和最后一条语句是一样的所以我们关注的代码其实是中间的那部分我们把循环看作一个整体忽略头尾循环判断的开销那么这两个算法其实就是n次与1次的差距。算法好坏显而易见。
我们再来延伸一下上面这个例子 这个例子中i从1到100每次都要让j循环100次而当中的x和sumsumx其实就是123…10000也就是100^2次所以这个算法当中循环部分的代码整体需要执行n^2忽略循环体头尾的开销次。
显然这个算法的执行次数对于同样的输入规模n100要多于前面两种算法这个算法的执行时间随着n的增加也将远远多于前面两个。
此时你会看到测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。
我们不关心编写程序所用的程序设计语言是什么也不关心这些程序将跑在什么样的计算机中我们只关心它所实现的算法。这样不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作最终在分析程序的运行时间时最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
可以从问题描述中得到启示同样问题的输入规模是n求和算法的第一种求12…n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是fnn显然运行100次的同一段代码规模是运算10次的10倍。而第二种无论n为多少运行次数都为1即fn1第三种运算100次是运算10次的100倍。因为它是fnn2。
我们在分析一个算法的运行时间时重要的是把基本操作的数量与输入规模关联起来即基本操作的数量必须表示成输入规模的函数。 我们可以这样认为随着n值的越来越大它们在时间效率上的差异也就越来越大。好比你们当中有些人每天都在学习我指有用的学习而不是只为考试的死读书每天都在进步而另一些人打打游戏睡睡大觉。入校时大家都一样但毕业时结果可能就大不一样前者名企争抢着要后者求职无门。 5.3 函数的渐近增长
我们现在来判断一下两个算法A和B哪个更好。假设两个算法的输入规模都是n算法A要做2n3次操作你可以理解为先有一个n次的循环执行完成后再有一个n次循环最后有三次赋值或运算共2n3次操作。算法B要做3n1次操作。你觉得它们谁更快呢
准确说来答案是不一定的 当n1时算法A效率不如算法B次数比算法B要多一次。而当n2时两者效率相同当n 2时算法A就开始优于算法B了随着n的增加算法A比算法B越来越好了执行的次数比B要少。于是我们可以得出结论算法A总体上要好过算法B。
此时我们给出这样的定义输入规模n在没有限制的情况下只要超过一个数值N这个函数就总是大于另一个函数我们称函数是渐近增长的。
函数的渐近增长给定两个函数fn和gn如果存在一个整数N使得对于所有的n Nfn总是比gn大那么我们说fn的增长渐近快于gn。
从中我们发现随着n的增大后面的3还是1其实是不影响最终的算法变化的例如算法A′与算法B′所以我们可以忽略这些加法常数。后面的例子这样的常数被忽略的意义可能会更加明显。
我们来看第二个例子算法C是4n8算法D是2n^21。 当n≤3的时候算法C要差于算法D因为算法C次数比较多但当n 3后算法C的优势就越来越优于算法D了到后来更是远远胜过。而当后面的常数去掉后我们发现其实结果没有发生改变。甚至我们再观察发现哪怕去掉与n相乘的常数这样的结果也没发生改变算法C′的次数随着n的增长还是远小于算法D′。也就是说与最高次项相乘的常数并不重要。
判断一个算法的效率时函数中的常数和其他次要项常常可以忽略而更应该关注主项最高阶项的系数。判断一个算法好不好我们只通过少量的数据是不能做出准确判断的。根据刚才的几个样例我们发现如果我们可以对比这几个算法的关键执行次数函数的渐近增长性基本就可以分析出某个算法随着n的增大它会越来越优于另一算法或者越来越差于另一算法。这其实就是事前估算方法的理论依据通过算法时间复杂度来估算算法时间效率。 5.4 算法时间复杂度
在进行算法分析时语句总的执行次数Tn是关于问题规模n的函数进而分析Tn随n的变化情况并确定Tn的数量级。算法的时间复杂度也就是算法的时间量度记作TnO(f(n))。它表示随问题规模n的增大算法执行时间的增长率和fn的增长率相同称作算法的渐近时间复杂度简称为时间复杂度。其中fn是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法我们称之为大O记法。
一般情况下随着n的增大T(n)增长最慢的算法为最优算法。
显然由此算法时间复杂度的定义可知我们的三个求和算法的时间复杂度分别为O(n)O(1)O(n2)。我们分别给它们取了非官方的名称O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶当然还有其他的一些阶我们之后会介绍。
5.5 推导大O阶方法
那么如何分析一个算法的时间复杂度呢即如何推导大O阶呢我们给出了下面的推导方法基本上这也就是总结前面我们举的例子。
推导大O阶
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中只保留最高阶项。
3.如果最高阶项存在且不是1则去除与这个项相乘的常数。得到的结果就是大O阶。
哈仿佛是得到了游戏攻略一样我们好像已经得到了一个推导算法时间复杂度的万能公式。可事实上分析一个算法的时间复杂度没有这么简单我们还需要多看几个例子。
a 常数阶
首先顺序结构的时间复杂度。下面这个算法也就是刚才的第二种算法高斯算法为什么时间复杂度不是O(3)而是O(1)。
这个算法的运行次数函数是fn3。根据我们推导大O阶的方法第一步就是把常数项3改为1。在保留最高阶项时发现它根本没有最高阶项所以这个算法的时间复杂度为O(1)。
另外我们试想一下如果这个算法当中的语句sum1n*n/2有10句即
事实上无论n为多少上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关n的多少执行时间恒定的算法我们称之为具有O(1)的时间复杂度又叫常数阶。
注意不管这个常数是多少我们都记作O(1)而不能是O(3)、O(12)等其他任何数字这是初学者常常犯的错误。
对于分支结构而言无论是真还是假执行的次数都是恒定的不会随着n的变大而发生变化所以单纯的分支结构不包含在循环结构中其时间复杂度也是O(1)。
b 线性阶
线性阶的循环结构会复杂很多。要确定某个算法的阶次我们常常需要确定某个特定语句或某个语句集运行的次数。因此我们要分析算法的复杂度关键就是要分析循环结构的运行情况。
下面这段代码它的循环的时间复杂度为O(n)因为循环体中的代码须要执行n次。 c 对数阶
下面的这段代码时间复杂度又是多少呢
由于每次count乘以2之后就距离n更近了一分。也就是说有多少个2相乘后大于n则会退出循环。由2xn得到xlog2n。所以这个循环的时间复杂度为O(logn)。 d 平方阶
下面例子是一个循环嵌套它的内循环刚才我们已经分析过时间复杂度为O(n)。 而对于外层的循环不过是内部这个时间复杂度为O(n)的语句再循环n次。所以这段代码的时间复杂度为O(n2)。如果外循环的循环次数改为了m时间复杂度就变为O(m×n)。
所以我们可以总结得出循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
那么下面这个循环嵌套它的时间复杂度是多少呢 由于当i0时内循环执行了n次当i1时执行了n1次……当in1时执行了1次。所以总的执行次数为 用我们推导大O阶的方法第一条没有加法常数不予考虑第二条只保留最高阶项因此保留n2/2第三条去除这个项相乘的常数也就是去除1/2最终这段代码的时间复杂度为O(n2)。
从这个例子我们也可以得到一个经验其实理解大O推导不算难难的是对数列的一些相关运算这更多的是考察你的数学知识和能力。 e 方法调用的时间复杂度 上面这段代码调用一个函数function。 函数体是打印这个参数。其实这很好理解function函数的时间复杂度是O(1)。所以整体的时间复杂度为O(n)。
假如function是下面这样的 事实上这和刚才举的例子是一样的只不过把嵌套内循环放到了函数中所以最终的时间复杂度为O(n^2)。
下面这段相对复杂的语句 它的执行次数 根据推导大O阶的方法最终这段代码的时间复杂度也是O(n2)。 6. 常见的时间复杂度 常用的时间复杂度所耗费的时间从小到大依次是 我们前面已经谈到了O(1)常数阶、O(logn)对数阶、O(n)线性阶、O(n2)平方阶等至于O(nlogn)我们将会在今后的课程中介绍而像O(n3)过大的n都会使得结果变得不现实。同样指数阶O(2n)和阶乘阶O(n!)等除非是很小的n值否则哪怕n只是100都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度一般我们都不去讨论它。 7. 最坏情况与平均情况
找东西有运气好的时候也有怎么也找不到的情况。但在现实中通常我们碰到的绝大多数既不是最好的也不是最坏的所以算下来是平均情况居多。
算法的分析也是类似我们查找一个有n个随机数字数组中的某个数字最好的情况是第一个数字就是那么算法的时间复杂度为O(1)但也有可能这个数字就在最后一个位置上待着那么算法的时间复杂度就是O(n)这是最坏的一种情况了。最坏情况运行时间是一种保证那就是运行时间将不会再坏了。在应用中这是一种最重要的需求通常除非特别指定我们提到的运行时间都是最坏情况的运行时间。
而平均运行时间也就是从概率的角度看这个数字在每一个位置的可能性是相同的所以平均的查找时间为n/2次后发现这个目标元素。
平均运行时间是所有情况中最有意义的因为它是期望的运行时间。也就是说我们运行一段程序代码时是希望看到平均运行时间的。可现实中平均运行时间很难通过分析得到一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析一种方法是计算所有情况的平均值这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下都是指最坏时间复杂度。 8. 算法空间复杂度
我们在写代码时完全可以用空间来换取时间比如说要判断某某年是不是闰年你可能会花一点心思写了一个算法而且由于是一个算法也就意味着每次给一个年份都是要通过计算得到是否是闰年的结果。还有另一个办法就是事先建立一个有2 050个元素的数组年数略比现实多一点然后把所有的年份按下标的数字对应如果是闰年此数组项的值就是1如果不是值为0。这样所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。此时我们的运算是最小化了但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现算法空间复杂度的计算公式记作S(n)O(f(n))其中n为问题的规模f(n)为语句关于n所占存储空间的函数。
一般情况下一个程序在机器上执行时除了需要存储程序本身的指令、常数、变量和输入数据外还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身和算法无关这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数则称此算法为原地工作空间复杂度为O(1)。
通常我们都使用“时间复杂度”来指运行时间的需求使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时通常都是指时间复杂度。显然我们这本书重点要讲的还是算法的时间复杂度的问题。
