时间复杂度度详解
时间复杂度是衡量算法性能的重要指标，用来描述算法随着输入规模 n 增大，运行时间的增长趋势。以下是时间复杂度的核心概念与常见分类的详细讲解。
1. 时间复杂度的定义
时间复杂度反映了算法执行的 基本操作数量 与输入规模 n 的关系。它通常使用大 O表示法来表示，即：
其中 f(n)是输入规模 n 的函数，代表操作数量的增长速度。
2. 常见时间复杂度
时间复杂度可以分为常数、对数、线性、多项式、指数等不同增长级别。以下是常见时间复杂度，从快到慢排序：
2.1 O(1) - 常数时间复杂度
- 概念：无论输入规模多大，算法的运行时间都固定不变。
- 示例：访问数组某个索引元素。
arr = [1, 2, 3, 4]
x = arr[2] # O(1)
- 特性：效率极高，常见于简单的数学运算或直接访问。