复杂度分析

1. 算法效率评估

在算法设计中，我们先后追求以下两个层面的目标：

• 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
• 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。

1.1 评估方法

在能够解决问题的前提下，算法效率从两个维度进行考虑：时间效率和空间效率。效率评估方法主要分为两种：实际测试、理论估算。其中实际测试具有较大的局限性：

1. 难以排除测试环境的干扰因素。
2. 展开完整测试非常耗费资源。

1.2 理论估算介绍

实际工作中用的是理论估算比较多，理论估算又被称为复杂度分析，复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。这个定义有些拗口，我们可以将其分为三个重点来理解：

• "时间和空间资源"： 分别对应时间复杂度(time complexity)和空间复杂度(space complexity)。
• "随着输入数据大小的增加"： 意味着复杂度反映了算法运行效率与输入数据体量之间的关系。
• "时间和空间的增长趋势"： 表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的"快慢"。

复杂度分析克服了实际测试方法的弊端，体现在以下几个方面：

• 它无需实际运行代码，更加绿色节能。
• 它独立于测试环境，分析结果适用于所有运行平台。
• 它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。

2. 常见的程序控制结构

两种基本的程序控制结构：迭代、递归。两者的区别是：
迭代："自下而上"地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
递归："自上而下"地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止(基本情况的解是已知的)。

2.1 迭代

迭代(iteration)是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。迭代包含的有：for循环、while循环

2.2 递归

递归(recursion)是一种算法策略，通过函数调用自身来解决问题。它主要包含两个阶段：

• 递：程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到"终止条件"。
• 归：触发"终止条件"后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。 递归中比较特别的是尾递归：它是一种场景：如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。 以计算1+2+3+...+n为例:

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

比普通递归和尾递归，两者的求和操作的执行点是不同的:

• 普通递归：求和操作是在"归"的过程中执行的，每层返回后都要再执行一次求和操作。
• 尾递归：求和操作是在"递"的过程中执行的，"归"的过程只需层层返回。
  递归中还有一种递归树情形：比如处理斐波那契数列0,1,1,2,3,5,8...n，求该数列的第n个数字。代码实现的话：

/* 斐波那契数列：递归 */
int fib(int n) {
    // 终止条件 f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // 递归调用 f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // 返回结果 f(n)
    return res;
}

观察以上代码，我们在函数内递归调用了两个函数，这意味着从一个调用产生了两个调用分支。如图所示，这样不断递归调用下去，最终将产生一棵层数为 的递归树(recursion tree): 从本质上看，递归体现了"将问题分解为更小子问题"的思维范式，这种分治策略至关重要。

3. 时间复杂度

时间复杂度分析统计的不是算法运行时间(实际测试方式路子)，而是算法运行时间随着数据量变大时的增长趋势。比如：

// 算法 A 的时间复杂度：常数阶
void algorithm_A(int n) {
    System.out.println(0);
}
// 算法 B 的时间复杂度：线性阶
void algorithm_B(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(0);
    }
}
// 算法 C 的时间复杂度：常数阶
void algorithm_C(int n) {
    for (int i = 0; i < 1000000; i++) {
        System.out.println(0);
    }
}

3.1 时间复杂度分析的特点

1. 时间复杂度能够有效评估算法效率
2. 时间复杂度的推算方法更简便
3. 时间复杂度也存在一定的局限性
   例如，尽管算法 A 和 C 的时间复杂度相同，但实际运行时间差别很大。

3.2 函数渐近上界

给定一个输入大小为n的函数：

void algorithm(int n) {
    int a = 1;  // +1
    a = a + 1;  // +1
    a = a * 2;  // +1
    // 循环 n 次
    for (int i = 0; i < n; i++) { // +1(每轮都执行 i ++)
        System.out.println(0);    // +1
    }
}

设算法的操作数量是一个关于输入数据大小n的函数，记为T(n)，则以上函数的操作数量为： T(n)是一次函数，说明其运行时间的增长趋势是线性的，因此它的时间复杂度是线性阶。我们将线性阶的时间复杂度记为O(n),这种表示方法表示函数T(n)的渐近上界。时间复杂度分析本质上是计算"操作数量T(n)"的渐近上界，它具有明确的数学定义。

3.4 推算方法

1. 第一步：统计操作数量
   针对代码，逐行从上到下计算即可。然而，由于上述c*f(n)中的常数项c可以取任意大小，因此操作数量T(n)中的各种系数、常数项都可以忽略。根据此原则，可以总结出以下计数简化技巧:

• 忽略T(n)中的常数项。因为它们都与n无关，所以对时间复杂度不产生影响。
• 省略所有系数。例如，循环2n次、5n+1次等，都可以简化记为n次。
• 循环嵌套时使用乘法。

2. 第二步：判断渐近上界
   时间复杂度由T(n)中最高阶的项来决定。这是因为在n趋于无穷大时，最高阶的项将发挥主导作用，其他项的影响都可以忽略。n趋于无穷大:
   

3.5 常见类型

设输入数据大小为n,常见的时间复杂度类型如图所示(按照从低到高的顺序排列): 另外算法的时间效率往往不是固定的，而是与输入数据的分布有关。假设输入一个长度为n的数组nums, 其中nums由从1至n的数字组成，每个数字只出现一次；但元素顺序是随机打乱的，任务目标是返回元素1的索引。我们可以得出以下结论:

• 当nums=[123, 32, 2, 11....,1], 即最后一个元素是1时，需要完整遍历数组，达到最差时间复杂度O(n)
• 当nums=[1, ....123, 32, 2, 11], 即当首个元素为1时，无论数组多长都不需要继续遍历，达到最佳时间复杂度Ω(1)。 最差时间复杂度更为实用，因为它给出了一个效率安全值, 让我们可以放心地使用算法。通常使用最差时间复杂度作为算法效率的评判标准。

4. 空间复杂度

空间复杂度(space complexity)用于衡量算法占用内存空间随着数据量变大时的增长趋势。

4.1 算法相关空间

算法在运行过程中使用的内存空间主要包括以下几种:

• 输入空间：用于存储算法的输入数据。
• 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
• 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是"暂存空间"加上"输出空间"。
暂存空间可以进一步划分为三个部分:

• 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
• 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
• 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分，如图所示：

4.2 推算方法

我们通常只关注最差空间复杂度。这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。最差空间复杂度中的"最差"有两层含义:

1. 以最差输入数据为准: 当n<10时，空间复杂度为O(1),但当n>10时，初始化的数组nums占用O(n)空间，因此最差空间复杂度为O(n)。
2. 以算法运行中的峰值内存为准：例如，程序在执行最后一行之前，占用O(1)空间；当初始化数组nums时，程序占用O(n)空间，因此最差空间复杂度为O(n)。

void algorithm(int n) {
    int a = 0;                   // O(1)
    int[] b = new int[10000];    // O(1)
    if (n > 10)
        int[] nums = new int[n]; // O(n)
}

在递归函数中，需要注意统计栈帧空间。

4.3 常见类型

设输入数据大小为n，下图展示了常见的空间复杂度类型(从低到高排列):

5. 权衡时间与空间

理想情况下，我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况中，同时优化时间复杂度和空间复杂度通常非常困难。降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为"以空间换时间"；反之，则称为"以时间换空间"。
选择哪种思路取决于我们更看重哪个方面。在大多数情况下，时间比空间更宝贵，因此"以空间换时间"通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也非常重要。