
时间复杂度是衡量算法效率的重要指标,它表示算法执行所耗费的时间与算法中语句执行次数的关系。通常,我们只关注总运算次数表达式中受变量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表示法只是说有上界,但不是上确界。
此外,一个问题本身也有其复杂性。如果某个算法的复杂性达到问题复杂性的下界,则称为最佳算法。
总之,时间复杂度是衡量算法效率的重要指标,理解和掌握其计算方法对于优化算法具有重要意义。