算法的复杂度

一、时间复杂度

算法的时间复杂度是以算法中的最简单的重复操作为基准，估算运行一次该算法需要执行多少次该操作，这个次数就可以作为该算法的时间复杂度。

例如，对于如下算法：

void printArr(int *arr, int size)
{
    for(int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

我们将按照如下方式计算该算法的时间复杂度：

• 首先确定基准操作，我们的要求是尽量简单的主要重复操作。首先是尽量简单，如果我们以整个for循环作为基准，显然不符合尽量简单的要求，所以上述算法就只有将两个输出语句作为待选。其次是主要重复操作，对于上述算法的两个输出语句来说，只有for循环之内的输出语句是主要重复操作，故整个计算过程将以for循环内的输出语句作为基准操作。
• 然后计算运行一次该算法需要执行多少次该基准操作，很显然，这个次数和size挂钩，我们将这样的数据称之为输入规模 $n$。显然，上述算法需要执行size的常数倍次基准操作，具体为size次。

1. 大 $O$ 记法

对于处理同一件事情的两个算法，有些时候，它们之间相差的基准操作的次数可能很少，而当输入规模 $n$ 足够大的时候，这些相差的次数是完全可以忽略掉的。所以要表示一个算法的时间复杂度，我们并不精确计算一个算法执行了多少次基准操作，而是看一个算法执行基准操作次数的数量级，例如，如果一个算法需要执行 $n^2$ 次基准操作，而另一个算法需要 $n$ 次基准操作，那么毫无疑问当 $n$ 足够大时，后一个算法是一定优于前一个算法的，即使可能后一个算法实际上需要 $n+100$ 次基准操作。

对于前者，我们可以用一个与 $n$ 相关的函数 $T$ 来表示，即 $T(n)$，用于表示算法的总执行次数。这个总执行次数可以用另一种标记方法来表示，即 $O(f(n))$。其中的 $f(n)$ 就是 $T(n)$ 的最大数量级。例如当 $T(n)=2n^2+n+2$ 时，就可以表示为 $O(n^2)$，表示算法的时间复杂度随着输入规模进行平方级的增长。而 $n^2$ 的系数、更小的数量级 $n$ 以及常数项 $2$ 我们都进行了忽略，因为当 $n$ 足够大的时候，这些都可以进行忽略。从而我们就可以用足够简单的大 $O$ 记法来表示一个算法的时间复杂度了。

当然，需要注意的是，如果我们在比较两个算法的时间复杂度时并且它们的大 $O$ 记法相同时，这时就需要根据具体情况考虑是否忽略系数、更小的数量级以及常数项了。例如，一个 $T(n)=2n^2+n+2$ 的算法和一个 $T(n)=n^2+n+2$ 的算法，毫无疑问是后者更优，由于它们在一般情况下采用大 $O$ 记法是相同的，在比较时为了做出区分，应该将前者写作 $O(2n^2)$，后者写作 $O(n^2)$。更小的数量级和常数项则以此类推。

2. 常见数量级

常用的时间复杂度所耗费的时间从小到大依次是：

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$

通常情况下所能接受的最高时间复杂度就是 $O(n^2)$​，对于更高的时间复杂度，输入规模的增加会极大的影响运行时间。

另外，即使输入规模相同，一个算法可能会因为具体的处理过程而有时处理得快，有时处理得慢。根据这一点，可以将算法的运行情况分为三种：

• 最优情况：大多数算法的最优情况都是 $O(1)$ 的复杂度，故不具有讨论意义
• 最坏情况：即最坏情况下的时间复杂度，其他任何情况都不会比这个情况下的时间复杂度更高。一般在没有特殊说明的情况下，都是指最坏时间复杂度。
• 平均运行时间：即根据各种情况出现的概率和时间复杂度计算出来的平均运行时间。是所有情况中最有意义的，因为它是期望的运行时间。

二、空间复杂度

空间复杂度的计算方式和时间复杂度基本相同，且更好进行估计，即估计算法需要多少额外空间即可。

其表示方法也使用大 $O$ 记法，同样是与输入规模相关的函数。

通常，我们希望空间复杂度保持最低，即 $O(1)$。但有时通过部分的空间复杂度可以显著降低算法的时间复杂度，所以对于算法而言合理的空间复杂度也是非常重要的。