时间复杂度基础

学习目标

本节学习时间复杂度的基本含义。

时间复杂度不是精确描述程序运行了多少秒，而是描述随着输入规模 $n$ 增大，程序执行步骤数量如何增长。它关注的是增长关系，而不是某一次运行的具体耗时。

什么是输入规模

输入规模通常用 $n$ 表示，它代表问题中需要处理的数据量。

在不同问题中， $n$ 的含义可能不同：

在线性表中， $n$ 可以表示元素个数。
在字符串处理中， $n$ 可以表示字符串长度。
在树结构中， $n$ 可以表示节点数量。
在图结构中，可能同时关注顶点数量 $V$ 和边数量 $E$ 。

分析复杂度前，必须先弄清楚输入规模是什么。如果输入规模没有定义清楚，复杂度分析就会变得模糊。

从顺序查找开始

顺序查找是理解时间复杂度最好的起点。它的思路很直接：从第一个元素开始，一个一个检查，直到找到目标元素，或者检查完所有元素。

bool contains(const vector<int>& numbers, int target) {
    for (int number : numbers) {
        if (number == target) {
            return true;
        }
    }
    return false;
}

boolean contains(int[] numbers, int target) {
    for (int number : numbers) {
        if (number == target) {
            return true;
        }
    }
    return false;
}

def contains(numbers, target):
    for number in numbers:
        if number == target:
            return True
    return False

bool Contains(int[] numbers, int target)
{
    foreach (int number in numbers)
    {
        if (number == target)
        {
            return true;
        }
    }

    return false;
}

这四段代码使用不同语言表达了同一个思想：逐个检查元素。

如果目标值刚好在第一个位置，只需要检查 1 次。如果目标值在最后一个位置，或者根本不存在，就需要检查 $n$ 次。随着元素数量增加，最坏情况下检查次数也会按比例增加。

因此，顺序查找的时间复杂度通常记为 $O(n)$ 。

关注关键操作次数

分析时间复杂度时，不需要把每一条语句都精确计数。我们更关心会随着输入规模增长而增长的关键操作。

在顺序查找中，关键操作是“比较当前元素是否等于目标值”。这个比较在最坏情况下会执行 $n$ 次，所以整体增长趋势是线性的。

如果有一个函数无论输入规模多大，都只执行固定次数的操作，那么它通常是常数时间复杂度，也就是 $O(1)$ 。

一个简单计数模型

可以用下面的方式理解时间复杂度。

假设一个算法的操作次数可以粗略表示为：

T(n) = 3n + 5

这里的 $3n$ 表示有一部分操作会随着 $n$ 增长， $5$ 表示固定操作次数。

当 $n$ 很大时，影响增长趋势的主要部分是 $n$ ，而不是前面的常数 3 或后面的常数 5。因此，这类算法通常记为 $O(n)$ 。

本节小结

时间复杂度描述的是输入规模变大时，执行步骤数量如何增长。

分析时要先明确输入规模，再找到会随输入规模增长的关键操作。顺序查找是典型的 $O(n)$ 算法，因为最坏情况下需要逐个检查所有元素。