03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？
执行效率是算法一个非常重要的考量指标。
为什么需要复杂度分析？
我们可以执行一遍代码，通过统计、监控得到算法的执行时间和占用内存大小（也叫事后统计法），但有以下局限性：
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
综上，我们需要一个不用具体的测试数据来测试，就可以粗略估算算法的执行效率的方法：
大O复杂度表示法
int cal(int n){
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
估算以上代码的执行时长：从 CPU 的角度来看，这段代码每一行执行类似的操作：读数据-运算-写数据。假设每行代码执行时间都相同，记为 unit_time 。
第 2、3 行代码分别需要 1 个 unit_time 的时长，第 4 行代码都运行 n 遍，需要 n * unit_time 的时长，第 5 行同样运行 n 遍，需要 n * unit_time 的时长，所以这段代码的执行总时长是： (2 + 2n) * unit_time 。
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
再看这段代码：第 2、3、4 行分别需要 1 个 unit_time ，第 5、6 行分别需要 n * unit_time ，第 7、 8 行则分别需要 n^2 * unit_time ，所以这段代码的执行总时长是： (3 + 2n + 2n^2 ) * unit_time。
所有代码的执行时长 T(n) 与每行代码执行次数n成正比，总结成一个公式：T(n) = O(f(n))
上述第一个例子可表示为 T(n) = O(2n + 2) ，第二个例子可表示为 T(n) = O(2n^2 + 2n + 3) 。这就是大O时间复杂度表示法，他表示的是代码执行时长随数据规模增长的变化趋势，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
公式中的低阶、常量、系数三部分并不左右增长趋势，所以可以忽略，只需记录最大量级即可。所以用大O表示法表示刚刚两段代码的时间复杂度，记为：T(n) = O(n) T(n) = O(n^2)
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
// 以上代码可先分别分析三部分的时间复杂度
// T1(n) = O(1)
// T2(n) = O(n)
// T3(n) = O(n^2)
// T(n) = T1(n) + T2(n) + T3(n) = max(O(1), O(n), O(n^2)) = O(n^2)
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
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;
}
// 第一段代码只看 cal() 函数执行，其时间复杂度 T1(n) = O(n),
// 但是循环体里执行了 f() ，f() 的时间复杂度 T2(n) = O(n),
// 所以以上代码的时间复杂度 T(n) = T1(n) * T2(n) = O(n^2)
几种常见时间复杂度实例分析
复杂度量级（按数量级递增）
- 常量阶
O(1) - 对数阶
O(logn) - 线性阶
O(n) - 线性对数阶
O(nlogn) - 平方阶
O(n^2)、立方阶O(n^3)、……k次方阶O(n^k) - 指数阶
O(2^n) - 阶乘阶
O(n!)
对于以上复杂度量级可粗略分为两类，多项式量级和非多项式量级。非多项式量级只有 O(2^n) 和 O(n!)。
时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial）问题，当数据规模 n 越来越大时，非多项式量级算法的执行时长会急剧增加。所以，此类算法非常低效。
-
O(1)：代码执行时长不随 n 的增大而变长，这样的代码时间复杂度记作O(1) -
O(logn)、O(nlogn)：
i = 1;
while (i <= n) {
i = i * 2;
}
// i 从 1 开始取值，每循环一次，自乘 2 ，直到 i > n ， 循环结束
// i 的取值是一个等比数列：1, 2, 4, 8, ...,2^x
// 当 2^x > n ,循环结束，即 x = log2n
// 这段代码的时间复杂度就是O(log2n)
实际上，不管是以几为底，对数阶的时间复杂度都记为 O(logn)，因为对数之间是可以互相转化的，而在大O复杂度表示法中，是忽略系数的。
理解了 O(logn) ，那么当时间复杂度是 O(logn) 的代码执行 n 遍，根据乘法法则，这样的代码时间复杂度就是 O(nlogn) 了。
-
O(m + n)、O(m * n)：由两个数据的规模决定时间复杂度
int cal(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 表示两个数据规模，无法评估谁的量级大
// 所以上述代码的时间复杂度 T(n) = O(m + n)
空间复杂度分析
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称是渐进空间复杂度（asymptotic space complexity）,表示算法的存储空间与数据规模之间的增长关系。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i < n; ++i) {
a[i] = i * j;
}
for (i = n - 1; i >= 0; --i) {
print out a[i];
}
}
// 第 2 行代码申请了一个空间存储变量 i，但是它是常量阶的，与 n 无关，可以忽略
// 第 3 行代码申请了一个大小为 n 的 int 类型数组，所以整段代码的空间复杂度就是 O(n)
常见的空间复杂度：O(1) O(n) O(n^2)
网友评论