算法的时间复杂度计算
计算一个算法时间复杂度,有以下几个步骤:
1.找基本运算(如乘法,加法,交换等)2.找问题规模(通常为n,有时是多个)3.求执行次数的函数f(n) 在求执行次数时,我们基本都是在找函数关系,如i
★★我们考虑复杂的多层循环嵌套的问题:
?通常两种:& 1.内外循环不相关,彼此独立: 解决办法:内循环执行次数乘外循环次数就可以了如题:
显然,该时间复杂度为c选项
& 2.内外循环相关(外循环影响内循环)
当然,这是种极不严谨的说法。意思是外循环每取一个不同的值,内循环每次对应不同的循环次数。我们通常用数学归纳法求解。
如冒泡排序问题。?
还有下题:?
图中我给出了数学归纳法的求解过程,基本上所有多循环问题都可以数学归纳法。涉及对数时请小心谨慎使用。
但是,这些都不是这篇博文的亮点,亮点是提出了一种错误的做法。
为何要提出这种做法,因为很有意思!不妨学会了,试看看。下面是冒泡排序的错误做法? 但是有意思的是,错误的做法得出了正确的答案。错误做法:取内,外循环的执行次数相乘 外:n-1次 内:n-1错的很显然,因为外循环内取一个值,内循环执行次数都不同。但是仍然得到了正确的结果O(n2)
为什么? 因为在错误的算法中,没有丢失规模的n的最高次幂。通常怎么求时间复杂度?时间函数表达式中,增长最快的项除以该项系数。既然最高次幂没有丢,显然是正确的结果。为什么要讲这种错误的做法,因为凭借这种做法,可以5秒看出答案。不信?
看看这题
? 我想我表达的意思够清楚了,内外循环相乘,通常可以做出时间复杂度的估计,同样得出正确的解。更快求解。考试中遇到这类题速度写上答案。把时间用在后面的算法设计中。时间充足的时候,在回头用数学归纳法求一遍确保稳妥。
时间复杂度题型很多,复习时间紧张,所以不多做介绍。以后有时间,笔者会整理出所有的时间复杂度的求解问题。
完。如有问题,请留言交流,不对地方请指正,邮箱[email protected]
?题外话:昨天笔者根据自己思路整理得到上述文章以后。翻王道论坛的数据结构一书章节归纳总结时,看到了和我这篇文章相似的思路。表述不一样,都一个意思。同样有提到数学归纳法~(我之前还以为这是我自己想出来的,没想到已经有前辈想到了)高手所见略同。不过他们没提供错误方法坑读者,哈哈 -_-|| ?
?