算法的时间复杂度计算

2015-08-09  KhanLau

计算一个算法时间复杂度,有以下几个步骤:

1.找基本运算(如乘法,加法,交换等)2.找问题规模(通常为n,有时是多个)3.求执行次数的函数f(n)    在求执行次数时,我们基本都是在找函数关系,如i<=n,i为计数器(i++),这个循环通常执行是n次;若i为平方时,次数为log2n对数。    由于最近太忙,没时间更博客紧张,故简而言之。    这些简单的时间复杂度就不再赘述,直接上稍复杂的求解问题。

★★我们考虑复杂的多层循环嵌套的问题:

通常两种:& 1.内外循环不相关,彼此独立:    解决办法:内循环执行次数乘外循环次数就可以了如题:

显然,该时间复杂度为c选项

& 2.内外循环相关(外循环影响内循环)

当然,这是种极不严谨的说法。意思是外循环每取一个不同的值,内循环每次对应不同的循环次数。我们通常用数学归纳法求解。

如冒泡排序问题。?

还有下题:

图中我给出了数学归纳法的求解过程,基本上所有多循环问题都可以数学归纳法。涉及对数时请小心谨慎使用。

但是,这些都不是这篇博文的亮点,亮点是提出了一种错误的做法。

为何要提出这种做法,因为很有意思!不妨学会了,试看看。下面是冒泡排序的错误做法?       但是有意思的是,错误的做法得出了正确的答案。错误做法:取内,外循环的执行次数相乘       外:n-1次   内:n-1错的很显然,因为外循环内取一个值,内循环执行次数都不同。但是仍然得到了正确的结果O(n2)    

        为什么?        因为在错误的算法中,没有丢失规模的n的最高次幂通常怎么求时间复杂度?时间函数表达式中,增长最快的项除以该项系数。既然最高次幂没有丢,显然是正确的结果。为什么要讲这种错误的做法,因为凭借这种做法,可以5秒看出答案。不信?

看看这题 

  我想我表达的意思够清楚了,内外循环相乘,通常可以做出时间复杂度的估计,同样得出正确的解。更快求解。考试中遇到这类题速度写上答案。把时间用在后面的算法设计中。时间充足的时候,在回头用数学归纳法求一遍确保稳妥。

时间复杂度题型很多,复习时间紧张,所以不多做介绍。以后有时间,笔者会整理出所有的时间复杂度的求解问题。

。如有问题,请留言交流,不对地方请指正,邮箱.crb912@126.com

题外话:昨天笔者根据自己思路整理得到上述文章以后。翻王道论坛的数据结构一书章节归纳总结时,看到了和我这篇文章相似的思路。表述不一样,都一个意思。同样有提到数学归纳法~(我之前还以为这是我自己想出来的,没想到已经有前辈想到了)高手所见略同。不过他们没提供错误方法坑读者,哈哈 -_-|| 

  

 




    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多