手机无线电通讯发展史

上图为不同类型的函数的增长趋势图，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

常见的算法时间复杂度由小到大依次为：Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<Ο(n2)<Ο(n3)<…<Ο(2^n)<Ο(n!)。

值得留意的是，算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围，在一定问题规范范围之前某一算法比另外一算法高效，而过了一个阈值之后，情况可能就相反了，通过上图我们可以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能上面算法的排序相反的原因。

如何推导时间复杂度

上面我们了解了时间复杂度的基本概念及表达式，那么实践中我们怎么样才能通过代码获得对应的表达式呢?这就涉及到求解算法复杂度。

求解算法复杂度一般分以下几个步骤：

• 找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
• 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
• 用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则：

• 用常数1取代运行时间中的所有加法常数;
• 只保留时间函数中的最高阶项;
• 如果最高阶项存在，则省去最高阶项前面的系数;

下面通过具体的实例来说明以上的推断步骤和规则。

时间复杂度实例

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：
 

前言

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项，也是每个高级程序员的必备技能。针对同一问题，可以有很多种算法来解决，但不同的算法在效率和占用存储空间上的区别可能会很大。

那么，通过什么指标来衡量算法的优劣呢?其中，上面提到的效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。

• 时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。
• 空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。

在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。

一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况。最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差。

通常，时间复杂度要比空间复杂度更容易出问题，更多研究的是时间复杂度，面试中如果没有特殊说明，讲的也是时间复杂度。

时间复杂度

要获得算法的时间复杂度，最直观的想法是把算法程序运行一遍，自然可以获得。但实践中往往受限于测试环境、数据规模等因素，直接测试算法要么难以实现，要么误差较大，而且理论上也没必要对每个算法都进行一遍测试，只需要找到一种评估指标，获得算法执行所消耗时间的基本趋势即可。

时间频度

通常，一个算法所花费的时间与代码语句执行的次数成正比，算法执行语句越多，消耗的时间也就越多。我们把一个算法中的语句执行次数称为时间频度，记作T(n)。

渐进时间复杂度

在时间频度T(n)中，n代表着问题的规模，当n不断变化时，T(n)也会不断地随之变化。那么，如果我们想知道T(n)随着n变化时会呈现出什么样的规律，那么就需要引入时间复杂度的概念。

一般情况下，算法基本操作的重复执行次数为问题规模n的某个函数，也就是用时间频度T(n)表示。如果存在某个函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值是不为零的常数，那么f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。

渐进时间复杂度用大写O表示，所以也称作大O表示法。算法的时间复杂度函数为：T(n)=O(f(n));

T(n)=O(f(n))表示存在一个常数C，使得在当n趋于正无穷时总有 T(n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。

常见的时间复杂度有：O(1)常数型;O(log n)对数型，O(n)线性型，O(nlog n)线性对数型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指数型。

（编辑：常州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!