算法时间复杂度分析(一)

都知道,数据结构和算法解决的问题是「快」和「省」,判断一个算法是否好,就需要对其的时间、空间复杂度进行分析。

例如:一个算法 F,一个数据 N

  • 当 N 中有 10 个元素时,算法 F 进行处理,需要 1 s
  • 当 N 中有 100 个元素时,算法 F 进行处理,需要 10 s
  • 当 N 中有 1000 个元素时,算法 F 进行处理,需要 100 s
  • ……

可以看出,随着数据规模的增长,算法处理需要的时间也在变化,要表达这个时间变化和数据 N 的关系,假设关系为 T(N),可写出公式:$T(N) = F(N)$。

大 O 复杂度表示法

在描述算法的时候,一般采用大 O 表示,又称渐进符号。

// 例子一
int sum(int n) {
    int sum = 0;            // 1
    int i = 1;              // 1
    for (; i <= n; ++i) {   // n
        sum = sum + i;      // n
    }
    return sum;
}
// 执行时间:T(n) = 2n + 2

// 例子二
int sum(int n) {
    int sum = 0;               // 1
    int i = 1;                 // 1
    int j = 1;                 // 1
    for (; i <= n; ++i) {      // n
        j = 1;                 // n
        for (; j <= n; ++j) {  // n * n
            sum = sum + i * j; // n * n
        }
    }
}
// 执行时间:T(n) = 2n^2 + 2n + 3

由上两个例子可以得出一个规律,所有代码的执行时间 T(n) 与每行代码的执行次数成正比。可把这个规律总结出一个公式:$$T(n) = O(f(n))$$

  • $T(n)$:代码执行的时间
  • $n$:数据规模大小
  • $f(n)$:每行代码执行次总和(因为是一个公式,所以用 f(n) 来表示)
  • $O$:表示代码的执行时间 T(n) 与 f(n) 表达式成正比

所以,上面代码中的两个例子分别为:$T(n) = O(2n + 2)$、$T(n) = O(2n^n + 2n + 3)$,这就是 大 O 表示法

在第二个例子中 $T(n) = O(2n^n + 2n + 3)$,分别对 n 进行取值,A = 2n^n、B = 2n、C = 3

  • 当 n = 10,A = 200,B = 20,C = 3
  • 当 n = 100,A = 20000,B = 200,C = 3
  • 当 n = 1000,A = 200000,B = 2000,C = 3
  • 当 n = 10000,A = 20000000,B = 20000,C = 3
  • ……

当数据集变大后,数量级大的部分增长速度远远超过了数量级小的地方,公式中的低阶、常量、系数三部分并不左右增长趋势,所以可以忽略,只需要记录最大量级即可。最终,上面两个例子的复杂度分别为:$T(n) = O(n)$、$T(n) = O(n^2)$。

时间复杂度分析

上面说了大 O 时间复杂度的表示方法,在进行一段代码的时间复杂度分析时,有三个比较实用的方法。

  1. 只关注循环次数最多的一段代码

    例如上面代码中的例子一,第 3、4 行代码都是常量级的执行时间,与 n 的大小无关,所以对复杂度没有影响,进行忽略。执行次数最多的是第 5、6 行代码,它执行了 n 次,所以复杂度为 $O(n)$。

  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度

    int cal(int n) {
    	int sum_1 = 0;
    	int p = 1;
    	for (; p < 100; ++p) {      // 100
    		sum_1 = sum_1 + p;
    	}
    
    	int sum_2 = 0;
    	int q = 1;
    	for (; q < n; ++q) {        // n
    		sum_2 = sum_2 + q;
    	}
     
    	int sum_3 = 0;
    	int i = 1;
    	int j = 1;
    	for (; i <= n; ++i) {       // n
    		j = 1; 
    		for (; j <= n; ++j) {     // n * n
    			sum_3 = sum_3 +  i * j;
    		}
    	}
    
    	return sum_1 + sum_2 + sum_3;
    }

    这里有三段代码,这时就可以分别分析三段代码的复杂度,把它们放在一起,再取一个量级最大的作为整段代码的复杂度。

    第一段为 100,是一个常量的执行时间,与 n 的规模无关,第二段和第三段分别为 $O(n)$ 和 $O(n^2)$,所以这段代码的复杂度为 $T(n) = O(n^2)$。

  3. 乘法法则:嵌套代码的复杂度 = 外层复杂度 x 内层复杂度

    假设:

    • $T1(n) = O(f(n))$
    • $T2(n) = O(f(n^2))$

    则:

    • $T(n) = T1(n) \times T2(n) = O(f(n)) \times O(f(n^2)) = O(f(n^3))$
    int cal(int n) {
    	int ret = 0; 
    	int i = 1;
    	for (; i < n; ++i) {
    		ret = ret + f(i);
    	} 
    } 
     
    int f(int n) {
    	int sum = 0;
    	int i = 1;
    	for (; i < n; ++i) {
    		sum = sum + i;
    	} 
    	return sum;
    }

    假设函数 f 是一个普通的操作,第 4 ~ 6 行的复杂度为 $T1(n) = O(n)$,但是函数 f 本身不是一个简单的操作,它自身的复杂度为:$T2(n) = O(n)$,所以整个函数 cal 复杂度应该为:$T(n) = T1(n) \times T2(n) = O(n^2)$。

常见时间复杂度

这里给出常用的复杂度,这些几乎覆盖了今后可接触的所有代码的复杂度量级。

  • 多项式量级
    • $O(1)$ — 常量阶
    • $O(logn)$ — 对数阶
    • $O(n)$ — 线性阶
    • $O(nlogn)$ — 线性对数阶
    • $O(n^2)$ — 平方阶
    • $O(n^3)$ — 立方阶
    • $O(n^K)$ — K 次方阶
  • 非多项式量级
    • $O(2^n)$ — 指数阶
    • $O(n!)$ — 阶乘阶

量级大小从上到下依次递增

通常把非多项式量级的算法问题叫做 NP (Non-Deterministic Polynomial,非确定多项式) 问题。当数据规模 n 越来越大时,非多项式量级算法的执行时间会急剧增加,求解问题的时间会无限增长,所以,非多项式时间复杂度的算法是非常低效的算法,不推荐使用。

1. O(1)

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码,如下所示,即便有三行代码,其复杂度也是 O(1),而不是 O(3)。

int i = 1;
int j = 2;
int sum = i + j;

只要代码的执行时间不随 n 的增大而增长,时间复杂度都记作 O(1)。也可以说 只要算法中不存在循环语句、递归语句,即使有成千上万行代码,其时间复杂度也是 O(1)

2. O(logn)、O(nlogn)

i = 1;
while (i <= n) {
    i = i * 2;
}

根据之前的分析方法,这里的代码第 3 行是执行次数最多的,所以,只要计算出这行代码被执行了多少次,就能知道整段代码的时间复杂度。

代码中,每一次循环 i 就乘以 2,当大于 n 时结束循环,变量 i 的取值就是一个等比数列:$2^0$、$2^1$、$2^2$ … $2^x$,只要知道 x 的值是多少,就知道代码的执行次数了 x = logn,所以代码的时间复杂度为 O(logn)。

将代码稍作修改,如下:

i = 1;
while (i <= n) {
    i = i * 3;
}

这段代码的时间复杂度为 $O(log_3 n)$,实际上,不管以 2 为底还是以 3 为底,都把所有的对数阶的时间复杂度记作 O(logn)。

而 O(nlogn),在上面讲过的乘法法则,如果一段代码的时间复杂度是 O(logn),同时这段代码执行了 n 次,那时间复杂度就是 O(nlogn)。例如归并排序、快速排序的时间复杂度都是 O(nlogn)。

3. O(m+n)

这种时间复杂度跟之前的不一样

int f(int m, int n) {
    int sum_1 = 0;
    int i = 1;
    for (; i < m; ++i) {
        sum_1 = sum_1 + i;
    }
    
    int sum_2 = 0;
    int j = 1;
    for (; j < n; ++j) {
        sum_2 = sum_2 + j;
    }
    return sum_1 + sum_2;
}

m 和 n 表示两个数据规模,像这样无法评估出 m 和 n 谁的量级大,就不能简单的省略其中一个。所以,上面代码的时间复杂度应该为 O(m + n)。

内容小结

时间复杂度也叫渐进时间复杂度,用于分析算法执行效率与数据规模之间的增长关系(粗略表示),越高阶复杂度的算法执行效率越低。

事先做复杂度分析并不是多此一举,分析后提供了一个很好的理论分析的方向,能让我们对程序或算法的执行效率有一个“感性”的认识。

复杂度分析法则:

  • 单段代码看高频:例如循环
  • 多段代码取最大:例如同时存在单循环和多循环,取多循环的复杂度
  • 嵌套代码求乘积:例如递归、多重循环
  • 多个规模求加法:例如方法有两个参数控制两个循环次数,取二者复杂度相加

如果觉得这篇文章不错,不妨

微信打赏 微信打赏
支付宝打赏 支付宝打赏
线性表之顺序存储
简述