本文共 1288 字，大约阅读时间需要 4 分钟。
时间复杂度，又称时间复杂性，是用来描述程序运行时间的长短的关键指标。它反映了程序的效率，能够帮助我们判断算法的优劣。
程序的时间复杂度是一个与问题规模相关的数学函数。问题规模通常指算法中需要重复执行的次数。例如，一个循环内的重复次数就是问题规模n。
由于计算机性能因环境而异，无法准确描述程序在特定计算机上的运行时间。因此，我们假设每个基本操作（如赋值、打印、返回值等）的执行时间相等，视为一个时间单位。通过统计程序中基本操作的数量，我们可以估算时间复杂度。
这种假设在同一台计算机上是合理的，因为在同一环境下，基本操作的执行时间单位不会有大的波动。因此，程序的运行时间主要取决于基本操作的数量，而不是具体的执行时间。
基本操作的定义
每个基本操作（如赋值、打印、算术运算、逻辑运算等）的执行时间为1个单位。我们需要统计程序中所有基本操作的总数。顺序结构的处理
顺序结构的时间复杂度是各基本操作时间复杂度的总和。例如，以下代码的时间复杂度为3：print("a")print("b")print("c")循环结构的处理
循环结构的时间复杂度是各循环层次的时间复杂度的乘积。例如，以下代码的最内层循环执行3次，外层循环也执行3次，总时间复杂度为3 × 3 = 9：for i in range(3): for j in range(3): print("i={}, j={}".format(i, j))分支结构的处理
分支结构的时间复杂度取各分支中最大的时间复杂度。例如，以下代码在第一个分支中执行n次操作，时间复杂度为n；在第二个分支中执行1次操作，时间复杂度为1。因此，整体时间复杂度为n。默认情况下的时间复杂度
如果没有特别说明，默认使用最坏时间复杂度。最坏时间复杂度保证了程序在最坏情况下完成工作所需的时间。时间复杂度通常用大O记法表示。例如，时间复杂度可以表示为T(n) = O(n^2)，表示程序的执行时间与n的平方成正比。
大O记法忽略了具体的常数系数和低次项，关注的是时间复杂度的增长趋势。常见的时间复杂度比较如下：
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
| 时间复杂度 | 描述 |
|---|---|
| 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) | 时间复杂度随输入规模呈幂级增长。 |
通过分析算法的时间复杂度，我们可以比较不同算法的效率，为程序的优化提供理论依据。
转载地址：http://uzppz.baihongyu.com/