0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 算法 2

  • 小酒馆老板
  • /
  • 2017/12/28 15:27:0


H2

算法

算法: 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。


H3

数据结构与算法关系

我们这门课程叫做数据结构,但很多时候我们会讲到算法,以及它们之间的关系,市场上也有不少书叫“数据结构与算法分析”这样的名字。
有人可能就要问了,那你到底直降数据结构,还是算法一起讲?它们之间是什么关系呢?干嘛要放在一起?
这个问题怎么回答。打个比方,今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院,抬头一看—《梁山伯》18:00开眼。嗯?怎么会这样?一问才知道,今天饰演祝英台的演员生病,所以梁山伯唱独角戏。真是搞笑了,这还有什么看头?
事实上,数据结构和算法也是类似的关系。只谈数据结构,当然也可以,我们可以在很短的时间就把几种重要的数据结构介绍完。听完后,很可能你没什么感觉,不知道这些数据结构有啥用处,但如果我们再把响应的算法拿出来讲一讲,你就会发现,深刻开始感慨:哦计算机界的前辈们,的确是一些很牛很牛的人,他们是很多看似难以解决或者没法解决的问题,变得如此的美妙和神奇。


H3

两种算法的比较

大家都已经学过一门计算机语言,不管学的哪一种,学的好不好,好歹都是可以写点小程序的了。现在我要求大家写一个1+2+3…+100 结果的程序,你应该怎么写呢?

大多数人会马上写出如下的代码(以下为Swift代码):

var sum = 0
for i in 1...100 {
    sum = sum + i
}
print("结果:",sum)

这是最简单的计算机程序之一,他就是一种算法,我不缺解释这段代码的额含义了。问题在于,你的第一直觉就是这样子写的,但是这样子写真的好吗?是不是最高效呢?
此时我们不得不吧伟大数学家 高斯的童年故事拿出来说一遍,也许你们在已经听过,但是不妨感受一下,天才当年是如何才华和天分的。
据说18世界的德国小村庄的高斯,上小学的一天,课堂很乱,就像我们平时在下面窃窃私语摆弄手机的同学一样,老师非常生气,后果也很严重。在临放学前,要求每个学生都要计算 1+2+3…+100的结果,谁先算出来谁先回家。
天才当然不会被这种问题难道,告诉很快就有了记过,是 5050.老师非常惊讶,因为他相比也是花了大功夫通过 1+2=3 3+3=6 6+4=10 计算出来的。为什么这个少年这么快就算出来了了
高斯解释道:

sum =  1+ 2+ 3+... +99 +100
sum =  100+ 99+ 98+... +2 +1
2xsum = 101+ 101+ 101+...101+ 101

如果使用程序表示就是

var i = 1
var n = 100
var sum = 0
sum = (i + n)*n/2
print("结果:",sum)

神通就是神通,他用的方法相当于另一种求等差数列的算法,不仅仅可以用于100,也可以加到1千,一万,一亿,也都是瞬间的事情。但如果用刚才的程序,显然计算机要循环 一千,一万,一亿次的加法运算。人脑比电脑算得快,似乎成为了现实。


H3

算法的定义

什么是算法呢?算法是描述解决问题的方法。算法(Algorithm)这个单词最早出现在波斯数学家阿勒 花刺子密在公寓825年(相当于我们中国的唐朝)缩写的《印度数学算法》中。如今普遍任何的对算法的定义式:

算法是解决特定问题步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作

刚才的例子我们也看到,对于给定的问题,是可以有多种算法来解决的。
那我就要问问你们,有没有通用的算法呀。这个问题其实很弱鸡,就相当于问,有没有包治百病的药一样。
现实世界的问题千奇百怪,算法当然也就千变万化,没有通用的算法可以解决所有的问题。甚至解决一个小问题,很优秀的算法不一定适合他
算法定义中,提到了指令,指令能被人或及其等计算装置执行。它可以是计算机指令,也可以是我们平时的语言文字。
为了解决某个或者某类问题,徐耀吧指令表示称一定的操作序列,操作序列包含了一组操作,每一个操作都完成特定的功能,这就是算法了。


H3

算法的特性

算法由五个基本特性: 输入,输出,有穷性,确定性和可行性。


H4

输入输出

输入和输出特性比较好理解,算法具有零个或多个输入。尽管对于绝对数算法来说,输入参数都是必要的,但是对于个别情况,如打印“Hello World”。这样的代码不徐耀任何擦输入参数,依次算法的输入可以是零个。算法具有至少一个或多个输出。算法是一定有输出的,不需要输出,你用这个算法干嘛,输出的形式可以是打印输出,也可以是返回一个或多个值等。


H4

有穷性

有穷性:只算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每个步骤都在可接受的时间范围内完成。 现实中经常会写出死循环的代码,这就不满足有穷性。当然这里有穷的概念并不是纯粹数学意义的,而是在实际应用中应当合理的,可以接受的“有边界”。你说你写一个算法,计算机要算上二十年,一定会结束,他在数学意义是有穷了,但是媳妇熬成婆了,算法的意义也就不大了


H4

确定性

确定性:算法的每一步骤都具有确定的含义,不会出现二义性。 算法在一定条件下,只有一条执行路径,相同的输出只有唯一的输出结果。算法的每个步骤都被精确的定义而无歧义。


H4

可行性

可行性:算法的每一步骤都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。 可行性意味着算法可以转换为程序上级运行,并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法,不是说理论上不能实现,而是因为过于复杂,我们目前的编程方法,工具和大脑限制了这个工作,不过这都是理论研究领域的问题,不属于我们现在要考虑的范围。


H3

算法设计的要求

刚才我们谈到了,算法不是唯一的。也就是说,同一个问题,可以有多种解决问题的算法,这可能让那些长年只左右标准答案题目的学生失望了,他们多么希望存在标准答案的,只有一个是正确的,把它背下来,需要的时候套用就可以了。不过话说回来,尽管算法不唯一,相对好的算法确实存在的。掌握好的算法,对我们解决问题很有帮助,否则前任的智慧我们不能利用,就都得自己从头研究了。那么什么才叫好的算法呢?


H4

正确性

正确性:算法的正确性是指算法至少应该具有输入输出和加工处理无歧义性,能正确反映文日的雪球,能够得到答案的正确答案
但是算法的“正确”通常在用法上有很大的茶杯,大体分为以下四个层次。

  1. 算法程序没有语法错误。
  2. 算法程序对于合法的输入数据能够产生满足徐耀的输出结果。
  3. 算法程序对于非法的输入数据能够给出满足规格说明的结果。
  4. 算法程序对于精心选择的,甚至刁难的测试数据都有满足需求的输出结果。
    对于这四层含义,层次1要求最低,但是仅仅没有语法错误实在谈不上是好算法,这就如同仅仅解决温饱,不能算是胜过幸福一样。而层次4是最困难的,我们几乎不能初一验证所有的输入都得到正确的结果。
    因此算法的正确性在大部分情况下都不能用程序来证明,而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的,代价非常昂贵。所一般情况下,我们把层次3作为一个算法是否正确的标准。
    H4

    可读性

    可读性:算法设计的另一目的是为了便于阅读,交流和理解。
    可读性高有助于人们理解算法,晦涩难懂的算法往往因含错误,不易被发现,并且南与调试和修改。
    我在很久以前曾经看到一个网友写的代码,它号称这程序是‘用史上最少代码实现俄罗斯方块’。因为我也写过了类似的小程序,所以项研究以下他是如何写的。由于他追求的是最少代码这样的极致,使得他的代码真的不好理解。也许除了计算机和他自己,绝大多数人是看不懂他的代码的。
    我们写代码的目的,一方是为了让计算机执行,但还有一个重要的目的是为了便与他人阅读,让人理解和交流,自己也可能阅读,如果可读性不好,时间长了,自己都不知道写了些什么。可读性是算法好坏很重要的标志。
    H4

    健壮性

    一个好的算法还应该能对输入数据不合法的请款做合适的处理。比如输入的时间或者距离不应该是负数等。
    健壮性:当输入数据不合法事,算法也能做出相关处理,而不是产生异常莫名其妙的结果。
    H4

    时间效率高和存储量低

    最后好的算法,还应该具备时间效率高和存储量低的特点。
    时间效率值得是算法的执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的效率低。存储量需求指的是算法在执行时间需要的最大存储空间,主要只算法程序运行时算占用的内存和外部硬盘存储空间。设计算法应该满足时间效率高和存储连最低的需求。 在生活中人们都希望或最少的钱,用最短的时间,班最大的是,算法也是一样的方法,用最少的存储空间,花最少的时间。半城同样的事儿就是好算法。求100个人的平均分,羽球全省的所有考生的成绩的平均分在占用时间和内存有非常大的差异的,我们自然视锥可以高效率和第存储量的算法来解决问题。

综上,好的算法,应该具有正确性,可读性,健壮性,高效率和低存储量的特征。


H3

算法效率的度量方法

刚才我们提到设计算法要提高效率。这里的效率大都是只算法的执行时间。那么我们如何度量一个算法的执行时间呢。
正所谓“是骡子是马,拉出来溜溜”。比较容易想到的方法就是。我们通过对算法的数据测试,利用计算机的即使功能,来计算不同算法的效率是高还是低。


H4

事后统计方法

事后统计方法:这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同的算法编制的程序的运行时间进行比较,从而确定算法效率的高低。
但是这种方法显然有很大的缺陷的:

  • 必须依据算法事先便只好程序,这通常需要花费大量的时间和经理。如果编织出来发现他根本是糟糕的算法,不是竹篮打水一场空吗?
  • 时间的比较依赖于计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣。要知道,现在的一台四核处理器的计算机,跟当年的 286 386 486 等老爷爷辈的机器相比,在处理算法的运算速度上,是不能相提并论的;而所用的操作系统,编译器,运行框架等软件的不同,也可以影响他们的结果;就算是同一台计算器,CPU的使用率和内存占用情况不一样,也会造成席位的差异。
  • 算法的测试数据设计困难,并且程序的运行时间往往还与测试数据的规模有很大的关系,效率高的算法在小的测试数据还得不到体现。比如10个数字的排序,不管用什么算法,差异几乎为0 ,而我们如果由一百万个随机数字的排序,那不同算法的差异就非常大了。那么我们为了比较算法,到底用多少数据来测试,这是很难判断的问题。

基于时候统计方法有这样那样的缺陷,我们考虑不予采纳。


H4

事先分析估算方法

我们的计算机前辈们,为了对算法的评判更科学,研究出了一种叫做事前分析估算的方法。
事前分析估算方法:在家算计程序编制前,一句统计方法对算法进行估算。
经过分析,我们发现,一个用高级程序语言编写的程序在计算机上运行时消耗的时间取决于下列因素:

  1. 算法采用的策略,方法
  2. 便意产生的代码质量
  3. 问题的输入规模
  4. 机器执行指令的速度

第一条当然是算法好坏的根本,第二条要有软件来支持,第四条要看硬件性能。也就是说抛开这些与计算机硬件,软件有关的因素,一个程序的运算时间,依赖于算法的好坏和问题的输入规模,所谓问题输入规模是指输入量的多少。
我们来看看今天刚上课觉的例子,两种求和的算法:
第一种算法:

var sum = 0               //  执行1次
for i in 1...100 {        //  执行100次
    sum = sum + i         //  执行100次
}
print("结果:",sum)         //  执行一次

第二种算法:

var i = 1                //  执行1次
var n = 100              //  执行1次
var sum = 0              //  执行1次
sum = (i + n)*n/2        //  执行1次
print("结果:",sum)        //  执行1次

显然第一种算法执行了1+(n+1)+n+1次即2n+3次;而第二种算法,是1+1+1+1+ =5次。事实上第二种算法的第一条和最后一条是一样的,所以我们关注的代码其实中间的部分,我们把循环看作一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是n次和1次的差距。悬法好坏显而易见
我们再来延伸一下例子:

var x = 0
var sum = 0
var n = 100

for i in 0...n {
    for j in 0...n {
        x = x+1              // 执行了nxn次
        sum = sum + x
    }
}
print("结果:",sum,",执行了:",x,"次.")

ps:这个例子,我使用了 Playground 书写的,在写完之后居然产生了卡顿感,甚至Xcode一度不可操作,出现了 小彩虹圈。所以算法消耗非常大。

这个例子中,i从1到100,每次都让j在执行100次,而当中的x++和sum = sum+x,其实就是1+2+3+…+10000,也就是100平方次,所以这个算法当中,循环部分的代码整体需要执行 n平方(忽略循环体头尾的开销)次。显然这个算法的执行次数对于同样输入规模n=100,要多与前面两种算法,这个算法执行时间随着n的增加也将远远多与前面两个。
此时你会看到,测定运行时间最可靠的方法就是计算对运行时间由小号的基本操作的执行次数。运行时间与这个计数成正比。
我们不关心编写程序所用的程序设计语言是什么,和不管这些程序泡在什么样的计算机中,我们只关心他所事先的算法。这样,不记那些循环索引的递增和循环终止条件,变量生病,打印结果等操纵。最终,在分析程序的运行时间时,最重要的是把程序看成独立于程序设计语言的算法或一系列步骤。
可以从问题描述中得到启示,同样问题的输入模式是n,求和算法的第一种,求1+2+…n徐耀一段代码执行n次。那么这个问题的输入规模是的操作数量是f(n)=n,显然运行100次的同一段代码规模是运行10次的10倍。而第二种,无论n为多少,n的运行次数都是1,即f(n)=1 ,第三种,运算100次是运算10次的100倍。因为他是f(n)=n*n。
我们在分析一个算法的运行时间时,重要的是把基础操作的数量和输入规模关联起来,即基础操作的数量必须表示称输入规模的函数。


Image Description
算法 效率比较示意图


我们可以这样认为,随着n值的越来越大,他们在时间效率上的差异也越来越大,好比你们当中有些人每天都在学习,我指的是有用的学习,而不是只为考试的死读书,每天都在进度,而另一些人,打打游戏,谁睡大觉,入校时大家都一样,但毕业结果可能就大不一样,前者名气争抢着要,后者求职无门。


H3

函数的渐进增长

我们现在来判断一下,两个算法 A和B那个更好,假设两个算法的输入规模都是n,算法A要做2n+3此操作,你可以裂解现有一个n次的循环,执行完成后,在做依次n的循环,最后还有三次的复制或运算。共2n+3次操作。算法B要做3n+1次操作。你觉的他们谁更快呢?
准确来说,答案是不一定的


Image Description
函数渐进增长示意图


当n=1时,算法A效率不如算法B(次数要比算法b多一次)。而当n=2时候,两者的效率相同;当n>2时i算法,算法A就开始由于算法B了,随着n的增加,算法A比算法B越来越好了。于是我们可以得出结论,算A总体上好过与算法B。
此时我们给出这样的定义,输入规模n在没有限制的情况下,只要超过一个数值N,这个函数就是总大雨量一个函数,我们成函数时渐进增长的。

函数的渐进增长:定给两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们就说f(n)的增长渐进快于g(n)。

从中我们发现,随着n的增加,后面的+3还是+1 其实不影响最终的算法变化的,例如算法 A‘和算法B’,所以我门可以胡恶略这些假发常数。后面的例子,这样的成熟忽略的意义可能会更加明显。

后面的例子也就不再多说了。判断一个算法的效率时,函数的常熟和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数。

判断一个算法好不好,我们只通过少量的数据是不能精确判断的。根据刚才几个阳历,我们发现,如果我们可以对比这几个算法的关键执行次数函数的渐进增长型,基本就可以分析处:某个算法,随着n的增加,他越来越有一另一算法,或者越来越差于另一个算法。 这其实就是事前估计算法的理论依据,通过算法时间复杂度来估算算法时间效率。


H3

算法时间复杂度


H4

算法时间复杂度定义

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)岁n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,几座:T(n)=O(f(n))。他表示岁问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,乘坐算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。
一般情况下,随着n的增大,T(n)增加最慢的算法为最有算法。
显然,由此算法时间复杂度的定义可知,我们分别给他们去了非官方的名字,O(1) 叫常数阶,O(n)叫线性阶,O(n平方)叫平方阶,当然,还有其他的一些阶,我们之后会介绍。


H4

推导大O阶方法

那么我们如何分析一个算法的时间复杂度呢?即如何推导大O阶呢?我们给出了下面的推导方法,基本上,这也是我们总结我们前面觉的例子。

推导大O阶:

  1. 用常数1取代运行时间所有的加法常数
  2. 在修改后的运行次数函数中,只保留最高项阶
  3. 如果最高阶项存在且不是1,则去除与这个项想成的常数。
    得到的结果就是大O阶。

哈,仿佛是得到了游戏攻略一样,我们好像已经得到了一个推导算法时间复杂度的万能公式。可事实上,分析一个算法的时间复杂度,没有那么简单,我们还徐耀多看几个自己。


H4

常数阶

首先顺序结构的时间复杂度。下面这个算法,也就是刚才的第二种算法(高斯算法),为什么时间复杂度不是O(5),而是O(1).

var i = 1                //  执行1次
var n = 100              //  执行1次
var sum = 0              //  执行1次
sum = (i + n)*n/2        //  执行1次
print("结果:",sum)        //  执行1次

这个算法的运行次数函数是f(n)=5.根据我们推导大O阶的方法,第一步就是把常数项5换成1.在保留最高位项阶时,他根本没有最高阶项,所以这个算法时间复杂度为O(1)。
另外,我们是试想以下,如果这个算法当中的次数sum = (i + n)*n/2由10句,即:

var i = 1                //  执行1次
var n = 100              //  执行1次
var sum = 0              //  执行1次
sum = (i + n)*n/2        //  执行1次 NO.1
sum = (i + n)*n/2        //  执行1次 NO.2
sum = (i + n)*n/2        //  执行1次 NO.3
sum = (i + n)*n/2        //  执行1次 NO.4
sum = (i + n)*n/2        //  执行1次 NO.5
sum = (i + n)*n/2        //  执行1次 NO.6
sum = (i + n)*n/2        //  执行1次 NO.7
sum = (i + n)*n/2        //  执行1次 NO.8
sum = (i + n)*n/2        //  执行1次 NO.9
sum = (i + n)*n/2        //  执行1次 NO.10
print("结果:",sum)        //  执行1次

事实上无论n为多少,上面两段代码就是3和12次执行的差异。这种与问题大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。
注意:不管这个常数是多少,我们都记做O(1),而不能是O(3),O(12)等其他任何数字,这也是初学者常常犯的错误。
对于分支结构而言,无论真,还是家,执行的次数都是恒定的,不会随着n的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1)。


H4

线性阶

线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数。因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况。
下面这段代码,他的循环的时间复杂度为O(n),因为循环体重的代码徐耀执行n次。

var sum = 0
for i in 1...100 {
    // 时间复杂度为O(1)的程序步骤序列
}

H4

对数阶

下面的代码,时间复杂度又是多少呢?

var count = 1
while(count < n){
  count = count*2
  // 时间复杂度为O(1)的程序步骤序列
}

由于每次count乘以2之后,就距离n更近了一分。也就是说,有多少个2相乘后大于n,则会推出循环。由2的X平方等到x=log2n。所以说这个循环的时间复杂度为O(logn)。


H4

平方阶

下面例子是一个循环嵌套,他的内循环我们已经分析过,时间复杂度为O(n).

for i in 0...n {
    for j in 0...n {
    // 时间复杂度为O(1)的程序步骤序列
    }
}

而对于外层的循环,不过是内部循环这个时间复杂度为O(n)的语句,再循环n次。所以这段代码的时间复杂度为O(n平方)
如果外循环的循环次数改为了m,其时间复杂度就为o(mxn)。

for i in 0...m {
    for j in 0...n {
    // 时间复杂度为O(1)的程序步骤序列
    }
}

所以我们可以总结得出,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。


H4

常见的时间复杂度

常见的复杂度如表


Image Description
常见的时间复杂度示意图


H4

最坏情况与平均情况

你早上上班出门后突然想起来,手机忘记带了,这年头,钥匙,钱包手机三大件,出门那样都不能少呀,于是回家找。打开门一看,手机就在门口玄关的台子上,原来是出门穿鞋时忘记拿了。这当然是比较好,基本没花什么时间寻找。可如果不是放在哪里,你就得进去到处找。
找东西有运气好的时候,也有怎么找也找不到情况。但在现实中,通常我们碰到的绝大多数既不是最好的也不是最坏的,所以算下来平均情况居多。
最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。在应用中,这是一种最重要的需求,通常,除非特别制定,我们提到的运行时间都是情况的运行时间。
平均运行时间是所有情况中最有意义的,因为它是预期的运行时间。也就是说,我们运行一段程序代码时,是希望看到平均运行时间的。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算出来的。
对算法的分析,一种方法是计算所有情况的平均值,这种时间复杂度的计算方法成为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度,这种方法成为最坏时间复杂度。一般没有特殊说明的情况下,都是指最坏时间复杂度。


H4

算法空间复杂度

我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。还有两一个办法就是通过,实现建立又2050个元素的数组,然后把所有的年份都按照用下表的数字对应。这样所谓的判断某一年是否为闰年,就变成了查找数组某一项的值又少的问题。此时我们的算法是最小化了,但是硬盘或内存中需要存储这个2050个0和1.
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要卡你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间时间,算法空间复杂度的计算公式记做:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占空间的函数。
一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令,常数,变量和输入数据外,还徐耀存储对数据操作的存储单元。如输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助但愿即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则成为次算法为原地工作,空间复杂度为O(1)。
通常,我们都是用“时间复杂度”来之运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地来使用“复杂度”时,通常都是指时间复杂度。现在我们这本书的重点还是在 时间复杂度。


H4

总结回顾

算法的定义:算法是解决特定问题求解步骤的描述,在计算机中为指令的的有限序列,并且每条指令表示一个或多个操作。
算法的特性:有穷性,确定性,可行性,输入和输出
算法的设计的要求:正确性,可读性,健壮性,高效率和低存储需求
算法特性和算法设计需求容易混,需要对比记忆。
算法的度量方法:事后统计方法(不科学,不准确),事前分析估算方法。
在讲解如何用时间分析估算方法之前,我们先给出了函数渐进增长的定义。
函数的渐进增长:给定两个函数f(n)和g(n),如果存在一个整数N,当n>N的事后,f(n)始终大于g(n)。那么我们就说f(n)的渐进增长比g(n)快。 于是我们得处一个结论,判断一个算法好不好,我们只通过少量的数据是不能作出准确判断的,如果我们可以对比算法的关键执行次数函数的渐进增长性,基本就可以分析出:某个算法,随着N的变大,他会越来越优于另一个算法,或者越来越差于另一个算法。
然后给出了算法时间复杂度的定义和推导大O阶的步骤。
推导大O阶:

  1. 用常数1取代运行时间所有的加法常数
  2. 在修改后的运行次数函数中,只保留最高项阶
  3. 如果最高阶项存在且不是1,则去除与这个项想成的常数。
    得到的结果就是大O阶。
    通过这个步骤,我们可以在得到算法的运算次数表达式后,很快就得到他的时间复杂度,即大O阶。同时我也提醒了大家,其实推导大O阶很容易,但如何得到运行次数的表达式确实很徐耀数学功底的。
专栏: 数据结构
标签: 数据结构 计算机基础