时间复杂度计算方法（简略）

一、什么是时间复杂度？

在计算机科学中，时间复杂度，又称时间复杂性，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。

简单定义：运行时间T与输入规模n之间的函数关系,T = f(n)。用于测量算法在时间方面的效率。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

二、计算方法。

求解算法的时间复杂度的具体步骤是：

1. 找出算法中的基本语句：即算法中执行次数最多的那条语句，通常是最内层循环的循环体。
2. 计算基本语句的执行次数的数量级；
3. 用大Ο记号表示算法的时间性能。

计算时间复杂度可以将其分为三类:

• 单层循环的时间复杂度计算
• 两层循环的时间复杂度计算
• 多层循环的时间复杂度计算

1、单层循环的时间复杂度计算

步骤:

1. 列出循环趟数t及每趟循环i的变化值。
2. 找到t与i的关系。
3. 确定循环停止条件。
4. 联立两式，解方程。
5. 写结果（最大数量级）。

i = n * n; while (i != 1) i = i/2;

2、两层循环的时间复杂度计算

步骤:

1. 列出外层循环中i的变化值。
2. 列出内层语句的执行次数。
3. 求和，写结果。

int m = 0, i, j; for (i = 1; i <= n; i++) for (j = 1; j <= 2*i; j++) m++;

3、多层循环的时间复杂度计算

for (i = 0; i <= n; i++) for (j = 0; j <= i; j++) for (k = 0; k < j; k++)

方法1：抽象为三维立体图计算体积

方法二：逐层求和

计算出每层循环次数，再相乘。

三、常见时间复杂度。

O(1): Constant Complexity 常数复杂度
O(log n):Logarithmic Complexity 对数复杂度
O(n):Linear Complexity 线性时间复杂度
O(n^2): N square Complexity 平方
O(n^3): N cubic Complexity 立方
O(2^n): Exponential Growth 指数
O(n!): Factorial 阶乘

时间复杂度从小到大排序：

O(1) < O(logn) < O(n) ＜ O(nlogn) ＜ O(n^2) ＜ O(n^3) ＜ O(2^n) ＜ O(n!) ＜ O(n^n)