算法的时间复杂度和问题规模_算法时间复杂度分析

发布于:2021-11-29 00:36:20





1. 算法优劣考虑项


在算法设计好之后,如何评定其优劣,以实现对算法的改进,就需要分析算法占用计算机资源的多少了。鉴于计算机主要是由运算和存储两部分构成,我们评定算法优劣也是通过其运行时间和占用内存空间来衡量,即时间复杂度分析和空间复杂度分析。


2. 算法时间复杂度分析


算法分析有事后分析统计方法(即编写算法对应程序,统计其执行时间)和事前估算分析方法(不考虑其它因素,认为算法的执行时间是问题规模n的函数)两种。因编写程序的语言和执行程序的环境(如电脑内存、CPU、周围温度)等因素不相同,会给事后分析统计造成标准无法统一,所以事前分析统计方法更为实用。


一个算法是由控*峁梗òㄋ承蚪峁梗≡窠峁梗方峁3种)和原操作(如下图求最大公约数算法中除语句④外都是原操作)构成,而算法执行时间是由控*峁褂朐僮鞴餐饔貌淖酆闲Ч






一般情况下(顺序结构不做考虑),控制语句出现的地方肯定伴随有原操作语句,而原操作语句出现的地方不一定伴随有控制语句的出现。又因为事前估计是采用统一的标准来估计不同算法的优劣,并不是使用确定的准确的执行时间来衡量不同的算法的优劣。所以,一个算法的执行时间快慢可以只由其中的原操作执行时间来考量。


算法执行时间大致等于原操作的执行次数(也称为频度,是问题规模n的函数,用T(n)表示)×单个原操作所需的时间(因单个原操作执行时间极短,可*似看做相等)。通过上式可以看出算法执行时间与T(n)成正比,即可以用T(n)衡量算法执行时间。算法时间复杂度是用T(n)的数量级来表示,记作T(n) =O(f(n)),“O”读作“大O”,是Order的简写,意指数量级,是指存在着正常量cn0(为一个足够大的正整数),使得



成立,所以算法时间复杂度也称为渐进时间复杂度。

3. 简化与分类


一般,对于问题规模为n的函数,循环体内的原操作数远大于非循环体内的原操作数,进一步简化可以仅采用最深层循环内的原操作(即算法中的基本操作)来进行算法时间复杂度分析。算法执行时间大致=基本操作所需的时间×其运算次数。即在算法时间复杂度分析时,可以计算T(n)时仅仅考虑基本操作的运算次数。


时间复杂度包括最坏时间复杂度、*均时间复杂度(即所有输入实例等概率出现情况下)和最好时间复杂度3种。我们以冒泡排序为例进行解释,如果序列本有序,我们只需比较n-1次,排序完成,则为最好情况下时间复杂度,为O(n);如果序列为逆序,则需要比较(n-1)+(n-2)+....+1 = n*(n-1)/2次,此时为最坏时间复杂度,且时间复杂度为O(n?);则*均复杂度也为O(n?)。我们一般讨论的为*均时间复杂度。


4. 总结


1)计算T(n)时仅考虑最深层循环内的原操作(即基本操作)的运算次数便可;


2)我们一般讨论的时间复杂度为*均时间复杂度;


3)一个没有循环的算法的执行时间与问题规模n无关,记作O(1),也称作常数阶;


4)一个只有一重循环的算法的执行时间与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶;


5)其余常用的算法时间复杂度还有*方阶O(n?)、立方阶O(n?)、对数阶O(log2n)、指数阶O(2n)等,且算法时间复杂度比较原则为:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n)

更多精彩内容,关注公众号:算法简堂

相关推荐

最新更新

猜你喜欢