程序优化--降低复杂度

程序优化的最核心的思路

第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

说明：常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等，而降低空间复杂度的方法就是数据结构，核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

降低复杂度案例

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

/**
 * @author 佛大Java程序员
 * @since 1.0.0
 */
public class AlgorithmTest4 {
    public static void main(String[] args) {
        AlgorithmTest4 algorithmTest4 = new AlgorithmTest4();
        algorithmTest4.s2_1();
        System.out.println("----------------------------------");
        algorithmTest4.s2_2();
    }

    /**
     * 方法一 ：时间复杂度为O( n³ )
     */
    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("i:"+ i + " j:" + j + " k:" +k);
                    }
                }
            }
        }
        System.out.println("方法一总共："+count+"组合");
    }

    /**
     *
     * 方法二：时间复杂度为O(n²)
     */
    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) % 2 == 0) && (100 - i * 7 - j * 3) >= 0) {
                    count += 1;
                    //System.out.println("i:"+ i + " j:" + j );
                }
            }
        }
        System.out.println("方法二总共："+count+"组合");
    }

}

方法一中使用了 3 层的 for 循环。从结构上来看，是很显然的 O( n³ ) 的时间复杂度。然而，仔细观察就会发现，代码中最内层的 for 循环是多余的。因为，当你确定了要用 i 张 7 元和 j 张 3 元时，只需要判断用有限个 2 元能否凑出 100 - 7* i - 3* j 元就可以了。

方法二中代码的结构由 3 层 for 循环，变成了 2 层 for 循环。很显然，时间复杂度就变成了O(n²) 。这样的代码改造，就是利用了方法论中的步骤二，将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

参考/好文：

拉勾教育 -- 重学数据结构与算法