时间复杂度

定义

时间复杂度是衡量一个算法执行时间随输入数据规模增长而变化的趋势。==它不表示算法执行的绝对时间，而是描述当输入规模 $n$ 增大时，算法执行语句次数的增长率。==通常使用大 O 表示法（Big O Notation）来表示，忽略常数项和低阶项，关注算法的渐进性能。

核心特点

• 渐进分析: 关注当输入规模 $n$ 趋于无穷大时，算法性能的变化趋势。
• 忽略常数项和低阶项: 大 O 表示法只保留最高阶项，并忽略其系数，因为在 $n$ 足够大时，最高阶项对增长率的影响最大。
• 最好、最坏、平均情况: - 最好情况时间复杂度: 算法在最理想输入下的执行时间。 - 最坏情况时间复杂度: 算法在最差输入下的执行时间，通常是衡量算法性能的重要指标。 - 平均情况时间复杂度: 算法在所有可能输入下的平均执行时间。

分类

常见的时间复杂度类型（按效率从高到低）：

• O(1): 常数时间复杂度，执行时间与输入规模无关。
• O(log n): 对数时间复杂度，如二分查找。
• O(n): 线性时间复杂度，执行时间与输入规模成正比，如遍历数组。
• O(n log n): 线性对数时间复杂度，如高效排序算法（归并排序、快速排序）。
• O(n^2): 平方时间复杂度，如冒泡排序、选择排序。
• O(2^n): 指数时间复杂度，通常效率很低，如某些递归算法。
• O(n!): 阶乘时间复杂度，效率极低，通常不可接受。

应用

• 算法设计与选择: 在设计新算法或选择现有算法时，时间复杂度是评估其可行性和效率的关键依据。
• 性能优化: 识别算法中的性能瓶颈，指导优化方向，例如将 O(n^2) 算法优化为 O(n log n)。
• 资源规划: 估算算法在处理大规模数据时所需的计算资源和时间。

优缺点

• 优点: - 提供量化标准，便于比较不同算法的效率。 - 帮助预测算法在处理大规模数据时的行为。 - 指导算法设计者进行性能优化。
• 缺点: - 忽略常数因子和低阶项，可能导致在小规模数据下与实际运行时间有偏差。 - 实际运行时间还受硬件、编程语言、编译器等多种因素影响。 - 仅关注渐进趋势，不代表绝对速度。
• 对比/区别: - 空间复杂度: 时间复杂度关注算法执行所需的时间资源，而空间复杂度关注算法执行所需占用的存储空间资源。两者都是衡量算法效率的重要指标，有时需要进行权衡。

相关概念

• 空间复杂度分析: 衡量算法执行所需存储空间随输入规模增长的趋势。
• 大O表示法: 描述函数渐进上界的一种数学符号，用于表示算法的时间和空间复杂度。
• 算法效率: 衡量算法性能的综合指标，包括时间效率和空间效率。
• 渐进分析: 在数学上分析函数在输入趋于无穷大时的行为。

案例

• O(1) 示例: 访问数组中的任意元素 arr[i]。

def get_element(arr, index):
    return arr[index]

• O(n) 示例: 遍历数组求和。

def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

• O(n^2) 示例: 嵌套循环，如冒泡排序。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

• O(log n) 示例: 二分查找。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

问答卡片

Q1：什么是时间复杂度

A：时间复杂度是衡量算法执行时间随输入数据规模增长而变化的趋势，通常用大 O 表示法表示。

Q2：大 O 表示法有什么特点？

A：大 O 表示法只关注算法执行次数的最高阶项，并忽略常数项和低阶项，以描述算法的渐进性能。

Q3：为什么时间复杂度不表示算法的绝对执行时间？

A：因为算法的绝对执行时间受多种因素影响，如硬件、编程语言、编译器等，时间复杂度只关注算法本身的效率趋势。

参考资料

• 《算法导论》
• 《数据结构与算法分析》
• 维基百科：时间复杂度
• GeeksforGeeks: Analysis of Algorithms | Set 1 (Introduction)