1. 复杂度：如何衡量程序运行的效率？

喜欢ヅ旅行 2023-02-22 13:31 22阅读 0赞

#### 复杂度是什么 ####

复杂度是衡量代码运行效率的重要的度量因素

#### 如何衡量复杂度 ####

> 1.  这段代码消耗的资源是什么

一般而言，代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是时间复杂度和空间复杂度

> 1.  这段代码对于资源的消耗是多少

我们不会关注这段代码对于资源消耗的绝对量，因为不管是时间还是空间，它们的消耗程度都与输入的数据量高度相关，输入数据少时消耗自然就少。为了更客观地衡量消耗程度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系

#### 如何计算复杂度 ####

复杂度是一个关于输入数据量 n 的函数

通常，复杂度的计算方法遵循以下几个原则：

*  首先，复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的
 *  其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了

#### 时间复杂度与代码结构的关系 ####

代码的时间复杂度，与代码的结构有非常强的关系，我们一起来看一些具体的例子

> 例 1，定义了一个数组 a = \[1, 4, 3\]，查找数组 a 中的最大值，代码如下：

public void s1() { 
        int a[] = {  1, 4, 3 };
        int max_val = -1;
        for (int i = 0; i < a.length; i++) { 
            if (a[i] > max_val) { 
                max_val = a[i];
            }
        }
        System.out.println(max_val);
    }

这个例子比较简单，实现方法就是，暂存当前最大值并把所有元素遍历一遍即可。因为代码的结构上需要使用一个 for 循环，对数组所有元素处理一遍，所以时间复杂度为 O(n)。

> 例2，下面的代码定义了一个数组 a = \[1, 3, 4, 3, 4, 1, 3\]，并会在这个数组中查找出现次数最多的那个数字

public void s1() { 
        int a[] = {  1, 3, 4, 3, 4, 1, 3 };
        int val_max = -1;
        int time_max = 0;
        int time_tmp = 0;
        for (int i = 0; i < a.length; i++) { 
            time_tmp = 0;
            for (int j = 0; j < a.length; j++) { 
                if (a[i] == a[j]) { 
                time_tmp += 1;
            }
            if (time_tmp > time_max) { 
                time_max = time_tmp;
                val_max = a[i];
            }
            }
        }
        System.out.println(val_max);
    }

这段代码中，我们采用了双层循环的方式计算：第一层循环，我们对数组中的每个元素进行遍历；第二层循环，对于每个元素计算出现的次数，并且通过当前元素次数 time\_tmp 和全局最大次数变量 time\_max 的大小关系，持续保存出现次数最多的那个元素及其出现次数。由于是双层循环，这段代码在时间方面的消耗就是 n\*n 的复杂度，也就是 O(n²)

在这里，我们给出一些经验性的结论：

*  一个顺序结构的代码，时间复杂度是 O(1)
 *  二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)
 *  一个简单的 for 循环，时间复杂度是 O(n)
 *  两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)
 *  两个嵌套的 for 循环，时间复杂度是 O(n²)

#### 降低时间复杂度的必要性 ####

假设某个计算任务需要处理 10万 条数据。你编写的代码：

*  如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右
 *  如果是 O(n)，那么计算的次数就是 10万 次左右
 *  如果这个工程师再厉害一些，能在 O(log n) 的复杂度下完成任务，那么计算的次数就是 17 次左右

#### 总结 ####

复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

*  它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度
 *  复杂度相加的时候，选择高者作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度
 *  O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关
 *  复杂度细分为时间复杂度和空间复杂度，其中时间复杂度与代码的结构设计高度相关；空间复杂度与代码中数据结构的选择高度相关

#### 拓展：降低复杂度的案例 ####

> 假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性

> 1.  暴力解法

public void s2_1() { 
        int count = 0;
        for (int i = 0; i <= (100 / 7); i++) { 
            for (int j = 0; j <= (100 / 3); j++) { 
                for (int k = 0; k <= (100 / 2); k++) { 
                    if (i * 7 + j * 3 + k * 2 == 100) { 
                        count += 1;
                    }
                }
            }
        }
        System.out.println(count);
    }
    使用了 3 层的 for 循环。从结构上来看，是很显然的 O( n³ ) 的时间复杂度

> 1.  无效操作处理

代码中最内层的 for 循环是多余的，主要确定了其余两个第三个也就能算出来

public void s2_2() { 
        int count = 0;
        for (int i = 0; i <= (100 / 7); i++) { 
            for (int j = 0; j <= (100 / 3); j++) { 
                if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) { 
                    count += 1;
                }
            }
        }
        System.out.println(count);
    }

代码的结构由 3 层 for 循环，变成了 2 层 for 循环。很显然，时间复杂度就变成了O(n²)

> 查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = \[1,2,3,4,5,5,6 \] 中，查找出现次数最多的数值

> 1.  暴力解法

public void s2_3() { 
        int a[] = {  1, 2, 3, 4, 5, 5, 6 };
        int val_max = -1;
        int time_max = 0;
        int time_tmp = 0;
        for (int i = 0; i < a.length; i++) { 
            time_tmp = 0;
            for (int j = 0; j < a.length; j++) { 
                if (a[i] == a[j]) { 
                time_tmp += 1;
            }
                if (time_tmp > time_max) { 
                    time_max = time_tmp;
                    val_max = a[i];
                }
            }
        }
        System.out.println(val_max);
    }

程序采用了两层的 for 循环，很显然时间复杂度就是 O(n²)。而且代码中，几乎没有冗余的无效计算。如果还需要再去优化，就要考虑采用一些数据结构方面的手段，来把时间复杂度转移到空间复杂度了

> 1.  时空转换，空间换时间

public void s2_4() { 
        int a[] = {  1, 2, 3, 4, 5, 5, 6 };
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < a.length; i++) { 
            if (d.containsKey(a[i])) { 
                d.put(a[i], d.get(a[i]) + 1);
            } else { 
                d.put(a[i], 1);
            }
        }
        int val_max = -1;
        int time_max = 0;
        for (Integer key : d.keySet()) { 
            if (d.get(key) > time_max) { 
                time_max = d.get(key);
                val_max = key;
            }
        }
        System.out.println(val_max);
    }

--------------------

参考：

[https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185\#/detail/pc?id=3339][https_kaiwu.lagou.com_course_courseInfo.htm_courseId_185_detail_pc_id_3339]  
[https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185\#/detail/pc?id=3340][https_kaiwu.lagou.com_course_courseInfo.htm_courseId_185_detail_pc_id_3340]

[https_kaiwu.lagou.com_course_courseInfo.htm_courseId_185_detail_pc_id_3339]: https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185#/detail/pc?id=3339
[https_kaiwu.lagou.com_course_courseInfo.htm_courseId_185_detail_pc_id_3340]: https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185#/detail/pc?id=3340