Android修炼系列（六），时间与空间复杂度的概念

本来是想将时间复杂度和空间复杂度的内容，放到后面的算法系列，但后想想，其实复杂度的审视应该是贯彻于整个开发过程之中的，应该是属于更大概念的“代码规范”的一部分，而不应局限在某个算法上。当然本文仅是以能用能理解为主，并不会深入到推倒公式的那种程度。

分析

当一个问题的算法被确定以后，那么接下来最重要的当然是评估该算法所用时间和占用内存资源的问题了，如果其运行时间超出了我们所能接受的底线，或者资源的占用多到当前设备不能满足的程度，那么对于我们来说，这个算法就是无用的，即使它能够正确的运行。

相比于执行完程序再事后统计其所用时间和占用空间的方法，理论层面的复杂度分析更有优势，主要表现在两点：

1、算法运行所在的设备，配置不同、运行环境的不同，都会给算法本身运行的实际时间和空间的计算带来偏差；

2、测试数据规模的大小，数据本身的特殊性与否，也会使实际的运行结果不具有普适性，不容易正确的反应算法的性能的一个真实情况。

那怎么从理论层面来分析复杂度呢？

大O标记法

关于 大O 标记法的相关描述，我就直接引用「数据结构与算法分析」的内容了：

一般来说，估计算法资源消耗所需的分析是一个理论问题，因此需要一套正式的系统架构，我们先从某些数学定义开始。

如果存在正常数 c 和 n_0n0 使得当N ≥ n_0n0 时，T(N) ≤ c f(N)，则记为T(N) = O( f(N) )。

定义的目的是建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，一般地宣称，比如说f(N) < g(N) ，是没有什么意义的。于是，我们比较它们的相对增长率。当将相对增长率应用到算法分析时，我们将会明白为什么它是重要的度量。

虽然对于较小的 N 值，1000N 要比 N^2N2 大，但 N^2N2 以更快的速度增长，因此 N^2N2 最终将是更大的函数。在这种情况下，N = 1000 是转折点。定义是说，最后总会存在某个点 n_0n0 ，从它以后 c · f(N) 总是至少与 T(N) 一样大，从而若忽略常数因子，则 f(N) 至少与 T(N)一样大。

在我们的例子中，T(N) = 1000N，f(N) = N^2N2，n_0n0 = 1000 而 c=1。我们也可以让 n_0n0 = 10 而 c = 100。因此，可以说 1000N = O(N^2N2)。这种记法称之为 大O标记法。人们常常不说“...级的”，而是说“大O...”。

同理还有下面的几个定义：

还有一点需要知道的是，当 T(N) = O( f(N) ) 时，我们是在保证函数 T(N) 是在以不快于 f(N)的速度增长，因此 f(N) 是T(N)的一个上界。这意味着 f(N) = Ω( T(N) )，于是我们说T(N)是f(N)的一个下界。”

时间复杂度分析

下面我们来看一段非常简单的代码

1    private static int getNum(int n) {

2        int currentNum = 0;

3        for(int i = 0; i < n; i++) {

4            currentNum += i*i;

5        }

6        return currentNum;

7    

在分析时，我们可以忽略调用方法、变量的声明和返回值的开销，所以我们只需要分析第2、3、4行的时间开销：

第2行占用1个时间单元；第4行的1次执行实际占用3个时间单元（1次乘法、1次加法、一次赋值），但是这么精确的计算是没有意义的，对于我们分析大O的结果也是无关紧要的，而且随着程序的复杂度提高这种方式也会变得越来越不可操作，（推导过程就省略了，直接上结论了，本节主要是用法层面）.

所以我们也记第4行的1次执行时间开销为1个时间单元，则 n 次执行开销为 n 个时间单元；同理第3行执行 n 次的时间开销也为 n 个时间单元，所以执行总开销为 (2n + 1) 个时间单元。所以f(N) = 2n+1，根据上文T(N) = c · f(N)到T(N) = O(2n + 1)的大O表示过程知道，我们可以抛弃一些前导的常数和抛弃低阶项，所以T(N) = O(N)。

知道了分析方法，下面我们再来看看其他复杂度的代码

1    private static void getNum(int n) {

2        int currentNum = 0;

3        for(int i = 0; i < n; i++) {

4            for(int j = 0; j < n; j++) {

5                currentNum++;

6            }

7        }

8   

通过上面代码我们可知：第2行1个单元时间，第3行 n 个单元时间，第4行 n^2n2 个单元时间，第5行 n^2n2 个单元时间，所以总时间开销f(N) = 2·n^2n2 + n + 1，所以复杂度T(N) = O(N^2N2)，当然O(N^3^)都是同理的。

1    private static void getNum(int n) {

2        int currentNum = 0;

3        for(int k = 0; k < n; k++) {

4            currentNum++;

5        }

6        for(int i = 0; i < n; i++) {

7            for(int j = 0; j < n; j++) {

8                currentNum++;

9            }

       }

通过上面代码我们可知：第2行1个单元时间，第3行 n 个单元时间，第4行 n 个单元时间，第6行 n 个单元时间，第7行 n^2n2 个单元时间，第8行 n^2n2 个单元时间，所以总时间开销f(N) = 2·n^2n2+3·n + 1，所以复杂度T(N) = O(N^2N2)。

1        if(condition) {

2            S1

3        } else {

4            S2

5        }

这是一段伪代码，在这里主要是分析 if 语句的复杂度，在一个 if 语句中，它的运行时间从不超过判断condition的运行时间加上 S1 和 S2 中运行时间长者的总的运行时间。

1    private static void getNum(int n) {

2        int currentNum = 0;

3        currentNum++;

4        if(currentNum > 0) {

5            currentNum--;

6        }

7    

通过上面的代码我们可知，第2行1个时间单元，第3行1个时间单元，第4行1个时间单元，第5行1个时间单元，所以总开销4个时间单元，所以复杂度T(N) = O(1)，注意这里不是O(4)哦。

1    private static void getNum(int n, int m) {

2        int currentNum = 0;

3        for(int i = 0; i < n; i++) {

4            currentNum++;

5        }

6        for(int j = 0; j < m; j++) {

7            currentNum++;

8        }

9  

通过上面的代码我们可知，第2行是1个单元时间，第3行是 n 个单元时间，第4行是 n 个单元时间，第6行是 m 个单元时间，第7行是 m 个时间单元，所以总的时间开销f(N) = 2·n +2·m + 1，所以复杂度T(N) = O(n+m)，同理，O(m·n)的复杂度也是同样分析。

1    private static void getNum(int n) {

2        int currentNum = 1;

3        while (currentNum <= n) {

4            currentNum *= 2;

5        }

6    

通过上面的代码我们可知，第2行需要1个单元时间；第3行每次执行需要1个单元时间，那么现在需要执行多少次呢？通过分析我们知道当 2^次次=n时 while 循环结束，所以次数 = log_2nlog2n，所以第3行总需要 log_2nlog2n 个单元时间；第4行同理也需要 log_2nlog2n 个单元时间，所以总时间开销f(N) = 2·log_2nlog2n + 1，所以复杂度T(N) = O(logn)，注意的是这里不但省略了常数，系数，还省略了底哦。

1    private static void getNum(int n) {

2        int currentNum = 1;

3        for(int i = 0; i < n; i++, currentNum = 1) {

4            while (currentNum <= n) {

5                currentNum *= 2;

6            }

7        }

8   

通过上面的代码我们可知，第2行1个单元时间，第3行 n 个单元时间，第4行根据上文我们需要n·log_2nlog2n个单元时间，第5行也需要n·log_2nlog2n个单元时间，所以总时间花销f(N) = 2·n·log_2nlog2n + n + 1，所以复杂度T(N) = O(n·logn)。

空间复杂度分析

上面我们简单介绍了几种常见的时间复杂度，空间的复杂度比时间复杂度要简单许多，下面就来分析一下空间的复杂度：

空间复杂度考量的是算法所需要的存储空间问题，一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元，若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。

1    private static void getNum(int n) {

2        int i = 0;

3        for(; i<n; i++){

4            i*=2;

5        }

6    

通过上面的代码我们知道，第2行我们只需要1个空间单元；第3行、第4行不需要额外的辅助空间单元，所以空间复杂度S(N) = O(1)，注意不是只有1个空间单元才是O(1)哦，如果空间单元是常量阶的复杂度都是O(1)哦。

1    private static void getNum(int n) {

2        int i = 0;

3        int[] array = new int[n];

4        for(; i<array.length; i++){

5            i*=2;

6        }

7    

根据上面的代码我们可知，第2行需要1个空间单元；第3行需要 n 个空间单元；第4行、第5行不需要额外的空间单元，所以总消耗f(n) = n + 1，所以空间复杂度S(N) = O(n)，其他情况的分析与时间复杂度分析方法一样，在这里就不详细介绍了。

好了，本文到这里就结束了，关于时间复杂度和空间复杂度的介绍应该够平时所需了。如果本文对你有用，来点个赞吧，大家的肯定也是阿呆i坚持写作的动力。

参考 1、数据结构与算法分析：机械工业出版社