@waterdkx 2016-03-06T08:32:03.000000Z 字数 2480 阅读 2209

夯实基础 -- 算法的时间复杂度

大一的时候因为转专业的缘故，C语言还没学过就开始跟着上数据结构的课，完全一头雾水。所以算法相关的知识点一直都是我不愿多提的短板。
现在已经是一个职业的程序员了，在解决了碰到的各式各样的问题后，越来越相信，想要在这个行业有长远的发展并小有成就，夯实基础知识是不能绕过的一个环节。之前一段时间对算法，对Linux，对三方库的源码之类的偏底层一点的东西都会有点恐惧感，但是慢慢的在工作中接触到了这些东西，觉得自己可以拿下，而且很有必要将其逐一拿下。所以，今天就从算法的时间复杂度开始下手，夯实基础，补回之前错过的。让自己的底盘更稳一点，才能走的更远。

定义

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity.

结合wiki的翻译，我的理解是这样的：

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。它的作用就如同一个返回输入的字符串参数的长度的函数。时间复杂度常用大写英文字母‘O’表述，表述时会忽略这个函数的低阶项和首项系数。使用这种方式时，时间复杂度其实是一个渐进值，它考察的是当输入值大小趋近于无穷时的情况。

还有一个更数学公式化的版本：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

计算方法

1. 计算出基本操作的执行次数T(n)
基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。
2. 计算出T(n)的数量级
求T(n)的数量级，只要将T(n)进行如下一些操作：

忽略常量、低次幂和最高次幂的系数

令f(n)=T(n)的数量级。

3. 用大‘O’来表示时间复杂度
当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。

Demo

   public void demo(int n) {
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < n; i++) {
            num1 += 1;
            for (int j = 1; j <= n; j *= 2) {
                num2 += num1;
            }
        }
    }

分析：

1.计算出基本操作的执行次数T(n)
语句：“int num1 = 0;int num2 = 0;int i = 0;”的频度都是1.
语句：“i < n;i++;num1 += 1;j=1;”的频度都为n.
语句：“j <= n; j *= 2; num2 += num1;”的频度为n * $\log{_2}n$

$T(n) = 2 + 4n + 3n * \log{_2}n$

2.计算出T(n)的数量级
忽略掉T(n)中的常量、低次幂和最高次幂的系数

$f(n) =n * \log{_2}n$

3. 用大O来表示时间复杂度

$lim(T(n)/f(n)) = (2+4n+3n * \log{_2}n) / (n*\log{_2}n) = 2*(1/n)*(1/\log{_2}n) + 4*(1/\log{_2}n) + 3$

当n趋向于无穷大，1/n趋向于0，1/ $\log{_2}n$ 趋向于0。所以极限等于3。

$T(n) = O(n * \log{_2}n )$

简化的计算步骤
仔细分析一下，决定算法时间复杂度的其实是最执行次数最多的语句。这个demo中的关键行是：

num2 += num1;

一般也是最内层的循环语句执行次数最多。
继续以上面的demo为例来分析：

执行次数最多的语句：

num2 += num1;

计算T(n)数量级

$T(n) = n * \log{_2}n$

$f(n) = n * \log{_2}n$
用大O来表示时间复杂度

$T(n) = O(n * \log{_2}n )$

一些补充说明

最坏时间复杂度
算法的时间复杂度不仅与语句频度有关，还与问题规模及输入实例中各元素的取值有关。一般如果不作特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的实际运行时间不会比估算的更长。

常见排序算法时间复杂度一览表

排序法	最差时间分析	平均时间复杂度	稳定性	空间复杂度
冒泡排序	$O(n{^2})$	$O(n{^2})$	稳定	$O(1)$
快速排序	$O(n{^2})$	$O(n * \log{_2}n )$	不稳定	$O(log{_2}n) - O(n)$
选择排序	$O(n{^2})$	$O(n{^2})$	稳定	$O(1)$
二叉树排序	$O(n{^2})$	$O(n * \log{_2}n )$	不一定	$O(n)$
插入排序	$O(n{^2})$	$O(n{^2})$	稳定	$O(1)$
堆排序	$O(n * \log{_2}n )$	$O(n * \log{_2}n )$	不稳定	$O(1)$

算法稳定性
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

夯实基础 -- 算法的时间复杂度

定义

计算方法

Demo

一些补充说明

参考文章

内容目录