算法是解决问题方案的准确而且完整的描述,通过一系列明确的指令解决问题。不同的算法在解决相同的问题时,所消耗的时间、空间效率不同。所以大家用时间复杂度和空间复杂度来衡量一个算法的优劣。[1]
二、算法的特征[1]
有穷性:一个合法的算法必然能通过有限个步骤解决问题。
确切性:算法的每个步骤都有明确的意义。
输入项:一个算法必然有0个或多个输入项。
输出项:一个算法必然有1个或多个输出项,没有结果输出的算法毫无意义
可行性:算法在解决问题时,每一个步骤都可以在有限的时间内完成。
三、时间复杂度&空间复杂度
1.时间复杂度
时间复杂度是一个函数,记为O(n),它用来描述算法运行的时间。[2]
那么让大家来举个栗子:
现在大家有一块蛋糕,要分给4个小朋友,在不考虑每个小朋友分到蛋糕大小相等的情况,大家要如何切蛋糕呢?
首先大家可以十字刀切蛋糕,这样两刀大家就可以把蛋糕分好了。还有什么办法呢?因为大家不关心蛋糕的大小,所以大家也可以同方向平行的切三刀把蛋糕分成四块。
好了,那么大家可以发现,大家可以用两刀解决问题、也可以用三刀解决问题,这里用了几刀解决了问题就是大家的时间复杂度。
通常大家使用算法的最坏情况复杂度,记为T(n),定义为任何大小的输入n所需要最大的运行时间。上面两个切蛋糕的方案,大家可以分别记为T(n)=2n\T(n)=3n。
接下来大家又遇到了新的问题了,有的小伙伴使用塑料餐刀切蛋糕用了五分钟才切好一刀,有的小伙伴使用40米大刀一秒切好一刀,他们都是用了两刀把蛋糕切好了,谁的速度更快呢?
这个问题就是在大家都是切了两刀,但是使用的切刀不同,也会导致大家分配蛋糕的时间变长。
所以大家使用了渐进时间复杂度:假设问题输入项有n个,当n趋于无穷大的时候,O(n)所得到的极限值。[3]
举个栗子,现在大家有两个算法,它们的时间复杂度分别为:
T(n)=3n^2+2n+1和T(n)=100n^4+999
先看一个公式:T(n)=3n^2+2n+1。当n趋于无穷大的时候,最后的1可以忽略不计了。接下来看3n^2和2n,大家发现当n越大的时候,两者差距就越大,当n趋于无穷大的时候,3n^2远远大于2n,所以2n大家也可以忽略不计了。最后大家只剩下3n^2,当n无穷大的时候,它再乘以3貌似对结果变得更大没有起到质的变化,所以大家省略掉3。最后大家剩下来最终的结果:T(n)=n^2
在看第二个公式:T(n)=100n^4+999。当n趋于无穷大的时候,999已经无足轻重了,自动忽略。从上一个公式的经验,大家就会自然忽略100,最终剩下T(n)=n^4
最终大家对比两个公式的优劣的时候,自然可以看出来当n越来越大的时候,第二个公式会比第一个公式耗时更长,所以第一个公式更好。
那么如果出现了公式:T(n)=3n^5+100n^3+10n^2,这种情况呢?按照大家第一个公式忽略的方案,当n趋于无穷大的时候,n^5要远远比n^3和n^2大,所以自然大家忽略掉100n^3和10n^2,只保留n^5,最终结果是T(n)=n^5。
最终大家来总结一下时间复杂度:
它是一个描述算法运行时间的函数O(n)
大家所讨论的时间复杂度常常使用的是最坏的情况T(n)
推导一个算法的时间复杂度,首先忽略常数、只保留函数中的最高阶、省去最高阶项的系数[4]
2.空间复杂度
空间复杂度是指在算法运行中时临时存储空间大小的量度,记为S(n)=O(f(n))。[5]简单来说就是,大家在代码执行中所占的内存大小。
那么如何去评定空间复杂度呢?方式和时间复杂度类似,大家也是根据输入项n来做判断。
举个栗子,现在大家要向一个数组插入一条新的数据,这个操作不会有额外的内存占有,所以它的空间复杂度是S(n)=O(1)
再举个栗子,大家现在要使用递归去解决一个问题,那么就存在每次向下递归时,都需要临时存储一下大家的数据,所以当递归至最底层时,临时存储了n个数据,所以它的空间复杂度是S(n)=O(n)
最终大家来总结一下空间复杂度:
它是指算法运行中所占用临时空间大小的量度
如果没有额外的临时空间占用,则空间复杂度为O(1)
额外占用空间是以输入项n为比例计算的