核心思想： 它衡量的是一个算法执行所需时间随着输入数据规模（n）增大而增长的趋势。注意，它不是一个具体的秒数，而是一个关于数据量 n 的函数。

为什么不用具体时间？
因为同一段代码在不同性能的电脑上运行时间完全不同。时间复杂度为我们提供了一个与机器无关的、纯粹从逻辑角度衡量算法效率的标尺。

2. 大 O 表示法

我们通常用大 O 表示法来描述时间复杂度。它表示的是算法运行时间的上限，即“最坏情况”下的趋势。

关键： 大 O 表示法关注的是当 n 变得非常大时，对运行时间影响最大的那个项，并且会忽略常数系数和低阶项。

为什么？ 因为当 n 足够大时（比如 n=1,000,000），n² 的影响力会远远超过 2n 或常数 5。

3. 从简单到复杂：常见时间复杂度解析

让我们通过几个常见的例子来感受一下。

例子 1：常数时间 O(1)

O(1) 表示算法的执行时间不随输入数据规模 n 的变化而变化。

python

def get_first_element(arr):
    return arr[0]  # 无论数组多长，我只取第一个元素

解释： 无论数组 arr 有 10 个元素还是 1000 万个元素，计算机完成“取出第 0 号位置的数据”这个操作所花的时间基本是一样的。它的时间曲线是一条水平线。

例子 2：线性时间 O(n)

O(n) 表示算法的执行时间与输入数据规模 n 成正比。

python

def print_all_elements(arr):
    for element in arr:   # 这个循环会执行 n 次
        print(element)

解释： 如果数组有 n 个元素，for 循环体内的 print 操作就会执行 n 次。如果 n 增加 10 倍，那么总的执行时间也大致增加 10 倍。它的时间曲线是一条斜线。

公式化思考：

• 循环 1 次：print 执行 1 次
• 循环 n 次：print 执行 n 次
• 总时间 T(n) = n * (单次 print 的时间) ≈ O(n)

例子 3：平方时间 O(n²)

O(n²) 表示算法的执行时间与 n 的平方成正比。通常出现在嵌套循环中。

python

def print_all_pairs(arr):
    n = len(arr)
    for i in range(n):        # 外层循环 n 次
        for j in range(n):    # 内层循环 n 次
            print(f"({arr[i]}, {arr[j]})") # 这一行被执行 n * n 次

解释：

• 当 i=0 时，内层 j 循环从 0 到 n-1，执行 n 次。
• 当 i=1 时，内层 j 循环又执行 n 次。
• …
• 当 i=n-1 时，内层 j 循环再执行 n 次。
• 所以，print 语句总共执行了 n * n = n² 次。

公式化思考：
总时间 T(n) = n (外层) * n (内层) * (单次打印时间) ≈ O(n²)

另一个常见变体：O(n*m)
如果遍历一个 nm 的二维数组，也是类似的双层循环，时间复杂度是 O(nm)。

例子 4：对数时间 O(log n)

O(log n) 是时间复杂度非常低的一种，随着 n 增大，时间增长非常缓慢。通常出现在每次操作后将问题规模减半的算法中（分治思想）。

最经典的例子是二分查找。

python

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2  # 找到中间点
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1       # 目标在右半部分，排除左半部分
        else:
            high = mid - 1      # 目标在左半部分，排除右半部分
    return -1

解释：
假设有一个已排序的数组，包含 n 个元素。

• 第 1 步：在 n 个元素中找。
• 第 2 步：根据比较结果，排除一半，在 n/2 个元素中找。
• 第 3 步：再排除一半，在 n/4 个元素中找。
• …
• 直到剩下 1 个元素。

这个过程就是不断地“除以 2”。我们需要计算的是：“n 除以多少次 2 会变成 1？”

公式化思考：
n / 2 / 2 / 2 … / 2 = 1 => n / (2^k) = 1 => n = 2^k
那么 k = log₂(n)
所以循环次数（即操作次数）是 log₂(n)，时间复杂度为 O(log n)。

注意： 在大 O 表示法中，我们忽略对数的底，统一写成 O(log n)。

4. 计算法则：如何分析一段代码？

当你面对一段复杂的代码时，可以遵循以下规则：

1. 看循环：循环是时间复杂度的主要贡献者。
2. 嵌套循环相乘：如果循环是嵌套的，将它们循环的次数相乘。
3. 顺序语句取最大：如果代码是顺序执行的（例如先执行一个 O(n) 的循环，再执行一个 O(n²) 的循环），那么总复杂度取最大值。即 O(n) + O(n²) = O(n²)。
4. 忽略常数和低阶项：
   • O(2n + 10) 简化为 O(n)
   • O(n² + n) 简化为 O(n²)
   • O(5) 简化为 O(1)

5. 综合练习

让我们分析下面这段代码：

python

def example_function(arr):
    n = len(arr)

    # 第一部分
    a = 0
    for i in range(100): # 循环 100 次，是常数
        a += i
    print(a) # O(1)

    # 第二部分
    for num in arr:      # 循环 n 次
        print(num)       # O(n)

    # 第三部分
    for i in range(n):   # 外层循环 n 次
        for j in range(n): # 内层循环 n 次
            print(i, j)    # O(n²)

    # 第四部分
    for i in range(n):   # 外层循环 n 次
        for j in range(10): # 内层循环 10 次，是常数
            print(i, j)    # O(10n) ≈ O(n)

逐步分析：

• 第一部分：循环 100 次，是常数，所以是 O(1)
• 第二部分：一个单循环，是 O(n)
• 第三部分：双层嵌套循环，是 O(n * n) = O(n²)
• 第四部分：虽然是双层循环，但内层循环次数固定为 10，所以是 O(n * 10) = O(n)

总复杂度：
我们将所有部分相加：O(1) + O(n) + O(n²) + O(n)

根据“取最大”的原则，O(n²) 是主导项。所以，这个函数的最终时间复杂度是 O(n²)。

总结与速查表

下面是一个常见时间复杂度增长趋势的总结，你可以直观地看到它们的差异（n 越大，差异越惊人）：

核心技巧就是多练习。 下次你看到一段代码，试着问自己：

1. 这段代码的核心循环是什么？
2. 循环的执行次数和输入规模 n 是什么关系？
3. 如果有多个循环，它们是嵌套的还是顺序的？

希望这个详细的解释能帮助你理解时间复杂度的计算！