算法基本知识及其时间复杂度的计算
(一)什么是算法?算法是解决特定问题的求解步骤的描述,在计算机中表现为指令的有序序列,并且每条指令表示一个或多个操作。
(二)算法的特性:(1)输入输出 :算法具有多个或零个输入,比如像“hello world”,这个代码不需要任何输入,此类代码不需要任何输入,因此算法可以是零输入的,但是算法至少应该有一个或多个输出;试想,一个算法如果不需要输出 ,那你用这个算法来干嘛。(2)有穷性:是指算法在执行完有限的步骤之后会自动结束而不是陷入无限循环,并且每一个步骤在可接受的时间内完成(你总不能一个算法让计算机运行好几十年才能运行出结果吧)。(3)确定性:算法的每一步骤都具有确定含义,不会出现二义性。即在相同的输入下对于确定的算法来讲只会有唯一的输出结果。(4)可行性:算法的每一步都必须是可行的,也就是说,每一步都可以通过执行有限的次数完成。
(三)算法设计的要求:(1)正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。但是算法的“正确”通常在用法上有很大的差别,大致分为以下几个层次。*1.算法没有语句错误。2.算法程序对于合法的输入数据能够产生满足要求的输出结果。3.算法程序对于非法的输入数据能够得到满足规格说明的结果。4.算法程序对于精心选择的、甚至刁难的测试数据都有满足要求的输出结果。*这四层含义对算法的要求也是从低到高排列,层次四最为困难,以至于我们几乎不可能逐一验证所有的输入都得到正确的输出结果。在一般情况下,我们把前三条作为一个算法是否正确的标准。(2)可读性:算法设计的另一目的就是为了方便阅读、理解和交流。你用很简单的代码实现了一个很复杂的功能,并且没有注释什么的,时间一久,可能自己都不知道当初到底写了些什么,因此可读性是衡量算法好坏的一个重要标志。(3)健壮性:当用户的输入数据不合理时,算法能给出相应的处理方案,而不是产生异常或者出现莫名其妙的结果。(4)时间效率高而储存量低:简单的讲就是花最少的材料办最大的事。
(四)算法的时间复杂度:用大写的O()来体现算法时间复杂度的记法,我们称之为大O记法。常见的推导大O阶的方法:
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。常见的大O阶分析:
1.常数阶。考虑如下代码
这个算法的运行函数为f(n) = 4;按照我们上面的办法,将常数4改为1,在保留最高阶项时发现他没有最高阶项,因此时间复杂度为O(1)。那如果是这样呢?
大家不用去数这一共执行了多少次,因为算法时间复杂度与问题的大小无关(即与n的大小无关),不管这个常数是多少,我们都记作O(1),而不能是O(4),O(14)等其他任何数字。执行时间恒定的算法我们称之为具有O(1)的时间复杂度,又叫常数阶。
2.线性阶:考虑如下代码:
该循环的时间复杂度为O(n),因为循环体中的代码必须执行n次。
3.对数阶:考虑如下代码:
每次循环以后,count都会乘以2,因此循环会在(假设)x个2相乘大于n的时候退出。因此可以得到2^x = n,即x = log2(n),所以这个循环的时间复杂度为O(logn)。
4.平方阶:两个都会循环n次的嵌套,时间复杂度自然就是O(n^2)。
如果是下面这种情况呢?
此时我们可以推导,外层循环执行第一次的时候内层循环执行n次,外层循环执行第二次的时候内层循环执行了n - 1次,外层循环第三次的时候内层循环执行n - 2次,以此类推我们可以得到总的执行次数为n + (n - 1) + (n - 2) +…+ 1 = n(n + 1) / 2=n^2 / 2 + n / 2。按照上述方法,第一步,没有 加法常数,因此不考虑;第二步,只保留最高阶项,变成了n^2/2;第三步:去除这个项相乘的常数,也就是去除1 / 2,最终这个代码的时间复杂度为O(n^2)。经过以上实例我们可以看出,大O阶的推导并不难,难的是你对数列以及一些数学基本知识的应用以及掌握情况,也就是说他更多的考察你的数学能力。
(五)常见的时间复杂度
常见的时间复杂度的耗费时间的大小依次是O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n!)。
最坏情况运行时间:指运行时间不会再坏了,在应用中,这是一项最重要的需求,一般而言,除非特别指定,我们提到的运行时间都是最坏情况的运行时间。