算法是如何一步一步优化的？-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法是如何一步一步优化的？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

英雄算法联盟 - 七月集训已经开始 6 天，八月算法集训将于 08月01日正式开始，目前已经提前开始报名，报名方式参见（八月算法集训报名），想要参加的同学，建议提早报名，因为对于算法零基础的同学，会有一些提前的准备工作，比如需要 1 - 5 天的时间完成预训练和九日集训提前养成刷题的习惯，再参加算法集训会更加有成效。

零、题目描述

视频版本👉🏻英雄哪里出来抖音。

给定一个长度为 n 的整数数组，数组下标从 0 开始。请返回上升四元组的数目，如果四元组满足如下条件：
1) 0 <= i < j < k < l < n
2) nums[i] < nums[k] < nums[j] < nums[l]
则这个四元组是上升的

一、 O ( n 4 ) O(n^4) O(n4) 理解错题意版本

既然是四元组，当然要定义四个变量啦。i、j、k、l分别代表四个递增的下标，定义四元组数目 ans，初始化为 0。
枚举 i从 0到 n-1
枚举 j从 i+1到 n-1
枚举 k从 j+1到 n-1
枚举 l从 k+1到 n-1
如果 a[i] < a[j]，并且 a[j] < a[k]，并且 a[k] < a[l]，那么就是一个满足条件的四元组，结果的值加一。最后返回 ans，就是我们要求的解啦。提交，错辣！

long long countQuadruplets(int* a, int n){
    int i, j, k, l;
    long long ans = 0;
    for(i = 0; i < n; ++i) {
        for(j = i + 1; j < n; ++j) {
            for(k = j + 1; k < n; ++k) {
                for(l = k + 1; l < n; ++l) {
                    if(a[i] < a[j] 
                    && a[j] < a[k] 
                    && a[k] < a[l]) ++ans;
                }
            }
        }
    }
    return ans;
}

二、 O ( n 4 ) O(n^4) O(n4) 超时版本

哦哦哦哦哦！j和 k的位置反了，这个题也太 baby 啦！（明明是自己没有认真审题啊），修改后运行，没什么问题，提交！

long long countQuadruplets(int* a, int n){
    int i, j, k, l;
    long long ans = 0;
    for(i = 0; i < n; ++i) {
        for(j = i + 1; j < n; ++j) {
            for(k = j + 1; k < n; ++k) {
                for(l = k + 1; l < n; ++l) {
                    if(a[i] < a[k] 
                    && a[k] < a[j] 
                    && a[j] < a[l]) ++ans;
                }
            }
        }
    }
    return ans;
}

超时啦！嘶……

三、 O ( n 4 ) O(n^4) O(n4) 简单优化后又错辣

哦哦哦哦哦！
a[i]和 a[k]完全不需要放到这个循环。提出来，如果 a[i]大于等于 a[k]，直接跳过，去掉这个判断。
a[k]和 a[j]也不需要放到这个循环。提出来，如果 a[k]大于等于 a[j]直接跳过，去掉这个判断。

long long countQuadruplets(int* a, int n){
    int i, j, k, l;
    long long ans = 0;
    for(i = 0; i < n; ++i) {
        for(j = i + 1; j < n; ++j) {
            for(k = j + 1; k < n; ++k) {
                if(a[i] >= a[k]) continue;
                if(a[k] >= a[j]) conitnue;
                for(l = k + 1; l < n; ++l) {
                    if(a[j] < a[l]) ++ans;
                }
            }
        }
    }
    return ans;
}

提交！编译错误？！

四、 O ( n 4 ) O(n^4) O(n4) 简单优化超时

哦哦哦哦哦！

long long countQuadruplets(int* a, int n){
    int i, j, k, l;
    long long ans = 0;
    for(i = 0; i < n; ++i) {
        for(j = i + 1; j < n; ++j) {
            for(k = j + 1; k < n; ++k) {
                if(a[i] >= a[k]) continue;
                if(a[k] >= a[j]) continue;
                for(l = k + 1; l < n; ++l) {
                    if(a[j] < a[l]) ++ans;
                }
            }
        }
    }
    return ans;
}

continue 拼错啦！恶业~改一下没问题，提交！又超时啦！

五、 O ( n 3 ) O(n^3) O(n3) 超时

啊爱爱爱爱啊！四个 for 循环， $O(n^4)$ 的时间复杂度，算算了，换成 $O (n^3)$ 的算法好了，枚举中间两个数，第一个数下标 j从 1到 n-1；第二个数下标 k从 j+1到 n-1，如果 a[k]大于等于 a[j]，则必然不满足条件的四元组，直接跳过。
否则定义一个less变量，记录 0到 j-1的数中小于 a[k]的数的个数；再定义一个bigger变量，记录 k+1到 n-1的数中大于 a[j]的数的个数。
然后利用乘法原理 less * bigger累加到 ans上，就把所有满足条件的四元组都统计出来啦！运行，没什么问题。

long long countQuadruplets(int* a, int n){
    int i, j, k, l;
    long long ans = 0;

    for(j = 1; j < n; ++j) {
        for(k = j + 1; k < n; ++k) {
            if(a[k] >= a[j]) {
                continue;
            }
            int less = 0;
            for(i = 0; i < j; ++i) {
                if(a[i] < a[k]) ++less;
            }
            int bigger = 0;
            for(l = k + 1; l < n; ++l) {
                if(a[l] > a[j]) ++bigger;
            }
            ans += less * bigger;
        }
    }
    return ans;
}

提交！又又超时啦！
这数据什么情况，哇靠！n最大是 4000，那 $O(n^3)$ 肯定就超时啦!起码得想个 $O(n^2)$ 的算法。

六、 O ( n 2 ) O(n^2) O(n2)

哦哦哦哦哦！
只要把求 less和 bigger
的 for 循环变成 O(1)不就好了！
1）定义一个宏maxn为4001，定义一个less矩阵和bigger矩阵，其中 less[i][j]代表 0到 i-1的数中小于 j的个数；其中 bigger[i][j]代表 i+1到 n-1的数中大于 j的个数；
2）对于任意的 j < k且 a[k] < a[j]，将 less[j][a[k]]和 bigger[k][a[j]]相乘，累加就是答案了。
3）然后就是求 less矩阵和 bigger矩阵的过程啦。封装成两个函数，先求 calcLess，less[0][i]代表第 0个数前面的数中，小于 i的数的个数，自然是 0，然后枚举 1到 n-1将 a[i-1]缓存到 x上，枚举 j从 1到 n，如果 x < j，就代表 less[i][j]就是 less[i-1][j]，加上一个数，也就是 x这个数，否则 less[i][j]的值，就是 less[i-1][j]的值。
4）用同样的方法计算 calcBigger，bigger[n-1][i]代表 n-1后面的数中，大于i的数的个数，显然是 0，然后逆序枚举 n-2到 0，将 a[i+1]缓存到 x上，枚举 j从 1到 n，如果 x > j，就代表 bigger[i][j]就是bigger[i+1][j]加上一个数，也就是 x这个数，否则 bigger[i][j]的值就是 bigger[i+1][j]的值。
5）最后把 less [j][ a[k] ]和 bigger[k][ a[j] ]累乘以后累加到 ans上。提交！

#define maxn 4001
int less[maxn][maxn], bigger[maxn][maxn];
// less[i][j] 代表 0 到 i-1 的数中，小于 j 的个数
// bigger[i][j] 代表 i+1 到 n-1 的数中，大于 j 的个数
// 对于任意 j < k， 且 a[k] < a[j]
// 累加 less[j][ a[k] ] * bigger[k][ a[j] ]

void calcLess(int *a, int n) {
    for(int i = 1; i <= n; ++i) {
        less[0][i] = 0;
    }
    for(int i = 1; i < n; ++i) {
        int x = a[i-1];
        for(int j = 1; j <= n; ++j) {
            if(x < j) {
                less[i][j] = less[i-1][j] + 1;
            }else {
                less[i][j] = less[i-1][j];
            }
        }
    }
}

void calcBigger(int *a, int n) {
    for(int i = 1; i <= n; ++i) {
        bigger[n-1][i] = 0;
    }
    for(int i = n-2; i >= 0; --i) {
        int x = a[i+1];
        for(int j = 1; j <= n; ++j) {
            if(x > j) {
                bigger[i][j] = bigger[i+1][j] + 1;
            }else {
                bigger[i][j] = bigger[i+1][j];
            }
        }
    }
}

long long countQuadruplets(int* a, int n){
    calcLess(a, n);
    calcBigger(a, n);
    long long ans = 0;
    for(int j = 0; j < n; ++j) {
        for(int k = j + 1; k < n; ++k) {
            if(a[k] < a[j]) {
                ans += less[j][ a[k] ] * bigger[k][ a[j] ];
            }
        }
    }
    return ans;
}