时间戳

首页 > 解决方案 > 降低递归函数的算法时间复杂度

c++ - 降低递归函数的算法时间复杂度

问题描述

这是函数 f(T,k) 的代码，其中

f(T,0)=∑(from i=1 to i≤len(T)) T[i], where len(T) is length of array T.
f(T,k)=∑(from i=1 to i≤len(T)) ∑(from j=i to j≤len(T)) f(T[i...j],k-1), for k>0, where len(T) is length 
of array T and T[i...j] is sub-array of T with elements form the i-th to the j-th position (T[i],T[i+1],...,T[j])

这是一个递归函数，我需要降低复杂性，但我不知道如何。
有人可以帮我吗？

这是问题文本：
1000000007 名玩家参与这场比赛，获胜者是随机选择的。为了使选择随机，该公司为选择该球员制定了严格的规则。首先他们用从 0 到 1000000006 的识别号给玩家编号。然后他们选择包含 N 个元素和数字 k 的数组 A。然后他们将获胜者定义为具有标识号 f (A, k) mod (100000007) 的玩家

#include <iostream>
#include <vector>

using namespace std;

int N,k,a;
vector<int>A;


int fja(vector<int>A,int k){
    long long suma=0;
    if(k==0){// If k==0 calculate the first said function
        for(auto it=A.begin();it!=A.end();it++)suma=(suma+(*it))%(1000000007);//Moduo is there because suma is very big
        return suma;
    }else{//If k>0 calculate the second function 
        int duzina=A.size();//duzina is length of A (T)
        for(int i=0;i<duzina;i++){//Going through the first and second sum of second function
            for(int j=i;j<duzina;j++){
                vector<int>b(A.begin()+i,A.begin()+j+1);//Creating new vector (array) to pass it into the new function call
                suma=(suma+fja(b,k-1))%(1000000007);//Moduo is there because suma is very big
            }
        }
        return suma;
    }

}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>k; //Number of elements and k
    for(int i=0;i<N;i++){
        cin>>a;
        A.push_back(a);//All the elements
    }



    cout<<fja(A,k);

}

标签： c++algorithmrecursiontime-complexity

解决方案

我实现了非递归版本，仅基于循环，但O(k * n^4)对于10^5N 和 k 的最大值，它会太慢。

我提供了递归解决方案供参考，它可以解决最多 10 个的 N 和 k，我的非递归解决方案最多可以解决 100 个的 N 和 k。

我确信可以通过算法优化在我的解决方案中删除一些循环。我仍然无法弄清楚如何解决非常大的 10^5 值的任务。

在当前 main() 函数中，N 和 k 都是 10，仅用于测试，只保留快速版本，您可以将 N 和 k 从 10 更改为 100 并注释掉 f_ref() 调用。f_ref() 是引用递归函数， f_fast() 是我更快的变体。

在线尝试！

#include <cstdint>
#include <vector>
#include <iostream>

typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

enum { mod = 100000007 };

i64 f_ref(std::vector<i64> const & T, size_t begin, size_t end, size_t k) {
    i64 sum = 0;
    if (k == 0)
        for (size_t i = begin; i < end; ++i)
            sum = (sum + T[i]) % mod;
    else
        for (size_t i = begin; i < end; ++i)
            for (size_t j = i; j < end; ++j)
                sum = (sum + f_ref(T, i, j + 1, k - 1)) % mod;
    return sum;
}

i64 f_fast(std::vector<i64> const & T, size_t k) {
    size_t N = T.size();
    std::vector<std::vector<i64>> mc, mn;
    for (size_t n = 1; n <= N; ++n) {
        mc.resize(mc.size() + 1);
        for (size_t j = 0; j < n; ++j)
            mc.back().push_back(((n + (n - 2 * j)) * (j + 1) / 2) % mod);
    }
    for (size_t ik = 0; ik + 1 < k; ++ik) {
        mn.clear();
        mn.resize(N);
        for (size_t n = 1; n <= N; ++n) {
            mn[n - 1].resize(n);
            for (size_t i = 0; i < n; ++i)
                for (size_t j = i; j < n; ++j)
                    for (size_t l = 0; l <= j - i; ++l)
                        mn[n - 1][i + l] = (mn[n - 1][i + l] + mc[j - i][l]) % mod;
        }
        mc = mn;
    }
    i64 sum = 0;
    for (size_t i = 0; i < N; ++i)
        sum = (sum + mc.back()[i] * (T[i] % mod)) % mod;
    return sum;
}

int main() {
    std::vector<i64> a;
    for (size_t i = 0; i < 10; ++i)
        a.push_back(i + 1);
    size_t k = 10;
    std::cout << f_ref(a, 0, a.size(), k) << " " << f_fast(a, k) << std::endl;
    return 0;
}

N = 10 和 k = 10 的输出：

78689325 78689325

N = 100 和 k = 100 的输出：

37190121

推荐阅读