时间复杂度是衡量算法效率的重要指标，它表示算法执行所耗费的时间与算法中语句执行次数的关系。通常，我们只关注总运算次数表达式中受变量n变化影响最大的那一项。例如，总运算次数表达式可以表示为：a*2^n + b*n^3 + c*n^2 + d*n*lg(n) + e*n + f。如果a ≠ 0，则时间复杂度为O(2^n)；若a = 0，b ≠ 0，则为O(n^3)；若a、b = 0，c ≠ 0，则为O(n^2)。以此类推。

例如，考虑以下循环结构：

1. for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
s++;

该循环执行了n * n次，因此其时间复杂度为O(n^2)。

2. for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
s++;

该循环执行了(n + (n - 1) + (n - 2) + ... + 1)≈(n^2)/2次，因此其时间复杂度同样为O(n^2)。

3. for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
s++;

该循环执行了(1 + 2 + 3 + ... + n)≈(n^2)/2次，同样为O(n^2)。

4. i = 1;
k = 0;
while (i <= n - 1) {
k += 10 * i;
i++;
}

该循环执行了n - 1≈n次，因此时间复杂度为O(n)。

5. for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
for (k = 1; k <= j; k++)
x = x + 1;

该嵌套循环执行了(1^2 + 2^2 + 3^2 + ... + n^2)≈(n^3)/3次，因此其时间复杂度为O(n^3)。

在时间复杂度中，log(2,n)与lg(n)是等价的，因为根据对数换底公式：log(a,b) = log(c,b) / log(c,a)，可以得出log(2,n) = log(2,10) * lg(n)，忽略掉系数，二者是等价的。

计算时间复杂度的方法是先找出算法的基本操作，然后确定其执行次数，再找出T(n)的同数量级。常见的数量级有1、log2n、n、nlog2n、n^2、n^3、2^n、n!。通常，随着问题规模n的增大，算法执行的时间的增长率和f(n)的增长率成正比。

常见的时间复杂度按数量级递增排列如下：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n^2)，立方阶O(n^3)，k次方阶O(n^k)，指数阶O(2^n)。其中，O(n)、O(n^2)、立方阶O(n^3)等为多项式阶时间复杂度；O(2^n)为指数阶时间复杂度，这类算法不实用；O(log2n)、O(nlog2n)等为非多项式阶时间复杂度，这类算法效率最高。

例如，给定以下算法：

for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
c[i][j] = 0; // 该步骤属于基本操作，执行次数：n^2
for (k = 1; k <= n; ++k) {
c[i][j] += a[i][k] * b[k][j]; // 该步骤属于基本操作，执行次数：n^3
}
}
}

则有T(n) = n^2 + n^3，根据上述同数量级，可以确定n^3为T(n)的同数量级，因此f(n) = n^3。根据T(n)/f(n)求极限可得到常数c，因此该算法的时间复杂度为T(n) = O(n^3)。

时间复杂性是指当输入量n逐渐加大时，时间复杂性的极限情形。通常使用大O表示法表示时间复杂性，即T(n) = O(f(n))。这里的“O”表示量级，如“二分检索是O(logn)的”，表示需要通过logn量级的步骤去检索一个规模为n的数组。大O表示法只是说有上界，但不是上确界。

此外，一个问题本身也有其复杂性。如果某个算法的复杂性达到问题复杂性的下界，则称为最佳算法。

总之，时间复杂度是衡量算法效率的重要指标，理解和掌握其计算方法对于优化算法具有重要意义。

下载本文