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