C++ 代码优化：从 O(9!) 到 O(1) 的时间复杂度优化

#include #include using namespace std;

double N; int arr[10]; bool num[10]; int total = 0;

void dfs(int step) { if (step == 10) { for (int i = 1; i <= 7; i++) { double first = 0; for (int n = 1; n <= i; n++) { first += pow(10,i-n)*arr[n]; } if (first >= N) { return; } for (int t = i + 1; t <= 8; t++) { double second = 0, third = 0; for (int n = i + 1; n <= t; n++) { second += pow(10, t - n) * arr[n]; } for (int n = t + 1; n <= 9; n++) { third += pow(10, 9 - n) * arr[n]; } if (N == first + (second / third)) { total++; } } } return; } for (int i = 1; i < 10; i++) { if (!num[i]) { num[i] = true; arr[step] = i; dfs(step + 1); num[i] = false; } } }

int main() { cin >> N; dfs(1); cout << total; }

这个怎么从时间方面优化内容：这个问题的时间复杂度是O(9!)，因为dfs函数会遍历所有的排列组合情况。要优化时间，可以考虑减少遍历的次数。

首先，我们可以观察到，第一个数的范围是1到7，第二个数的范围是第一个数的下一个位置到8，第三个数的范围是第二个数的下一个位置到9。所以可以使用三个循环来遍历这三个数的范围，而不是使用dfs函数遍历所有的排列。

其次，我们可以在遍历的过程中，根据当前的数值计算出first、second和third的值，然后直接判断是否满足条件，而不是在dfs函数中再进行计算。这样可以减少计算的次数。

优化后的代码如下：

#include<iostream>
#include<cmath>
using namespace std;

double N;
int total = 0;

int main() {
    cin >> N;
    for (int i = 1; i <= 7; i++) {
        for (int j = i + 1; j <= 8; j++) {
            for (int k = j + 1; k <= 9; k++) {
                double first = 0, second = 0, third = 0;
                for (int n = 1; n <= i; n++) {
                    first += pow(10, i - n) * n;
                }
                for (int n = i + 1; n <= j; n++) {
                    second += pow(10, j - n) * n;
                }
                for (int n = j + 1; n <= k; n++) {
                    third += pow(10, k - n) * n;
                }
                if (N == first + (second / third)) {
                    total++;
                }
            }
        }
    }
    cout << total;
    return 0;
}

这样优化后的代码的时间复杂度是O(1)，不再依赖于输入的N的大小。