算法复杂度分析

算法效率评估

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

找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度。

时间效率：算法运行时间的长短。
空间效率：算法占用内存空间的大小。

简而言之，我们的目标是设计“既快又省”的数据结构与算法。而有效地评估算法效率至关重要，因为只有这样，我们才能将各种算法进行对比，进而指导算法设计与优化过程。

效率评估方法主要分为两种：实际测试、理论估算。

理论估算

由于实际测试具有较大的局限性，我们可以考虑仅通过一些计算来评估算法的效率。这种估算方法被称为渐近复杂度分析（asymptotic complexity analysis），简称复杂度分析。

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据规模之间的关系。它描述了随着输入数据规模的增加，算法执行所需时间和空间的增长趋势。

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

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

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

复杂度分析为我们提供了一把评估算法效率的“标尺”，使我们可以衡量执行某个算法所需的时间和空间资源，对比不同算法之间的效率。

时间复杂度

时间复杂度能够有效评估算法效率。
时间复杂度的推算方法更简便。
时间复杂度也存在一定的局限性。

函数渐进上界

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 ++）
        printf("%d", 0);            // +1
    }
}

设算法的操作数量是一个关于输入数据大小 n 的函数，记为 T(n)，则以上函数的操作数量为：T(n) = 3 + 2n

我们考虑当 n 为 ∞ 时(渐近上界) 3+2n == n, 我们会将其记为O(n),这个O(n)就是上面上面算法的时间复杂度.

大O记号表示T(n)的渐进上界

推算方法

先求T(n)
忽略 T(n) 中的常数
省略所有系数: 例如，循环 2n 次、5n次等，都可以简化记为 n 次，因为 n 前面的系数对时间复杂度没有影响。
循环嵌套时使用乘法
时间复杂度由 T(n)中最高阶的项来决定

void algorithm(int n) {
    int a = 1;  // +0（技巧 1）
    a = a + n;  // +0（技巧 1）
    // +n（技巧 2）
    for (int i = 0; i < 5 * n + 1; i++) {
        printf("%d", 0);
    }
    // +n*n（技巧 3）
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < n + 1; j++) {
            printf("%d", 0);
        }
    }
}