降低以下代码的时间复杂性

Question

以下代码是竞赛中问题陈述的解决方案。给出的时间限制为1s。该代码在5/7个测试用例中正常工作。对于其他情况，超过了时间限制。如何降低下面代码的时间复杂度？

编辑：问题陈述被定义为返回数字n的值或n/2、n/3、n/4之和，以最大值为准。例如，如果输入为24，则可以进一步减少或交换为12 8 6=26，12可以减少为6 4 3=13。8和6不应减少，因为这可能会降低值。最后的答案是13 8 6=27

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define lli long long int
using namespace std;

lli exchange(lli n){
    if(n<12)
        return n;

    else{

        lli sum=0;
        sum+=max(n/2,exchange(n/2));
        sum+=max(n/3,exchange(n/3));
        sum+=max(n/4,exchange(n/4));
        return sum;
    }
}

int main() {  
    lli t;
    cin>>t;
    while(t--){
        lli n;
        cin>>n;
        lli ans;
        ans=max(n,exchange(n));
        cout<<ans<<endl;
    }
    return 0;
}

Answer 1

任何算法的标准权衡之一是时间与空间；内存或磁盘空间越大，节省的时间就越多，反之亦然。在这种情况下，您需要在特定时间内运行，但似乎允许您使用机器的全部内存。因此，请注意，这个特定的算法经常请求它已经计算过的值，应该将它们全部保存起来以便快速查找。

事实上，通常不被认为特别快的Python可以在大约一秒钟内计算10²⁹⁵，尽管如果使用空结果缓存运行10³⁰⁰会遇到最大递归深度错误：

exchanged = {}
def exchange(n):
    if n in exchanged:
        value = exchanged[n]
    elif n < 12:
        exchanged[n] = value = n
    else:
        exchanged[n] = value = exchange(n//2) + exchange(n//3) + exchange(n//4)
    return value
exchange(10**295)

对于C，静态std::映射

是的，可以省略max部分，因为它是由

Answer 2

只是尝试一些想法。首先，if语句的“true”分支是编译器预加载指令的分支。通过将high-n分支设为默认分支，速度会快一点。

编辑：其他一些想法没有成功（没有更快）。然而，一个很有希望的方法是展开两个级别的递归。

exchange(n) = exchange(n/2) + exchange(n/3) + exchange(n/4)

exchange(n/2) = exchange(n/2/2) + exchange(n/3/2) + exchange(n/4/2) 
exchange(n/3) = exchange(n/2/3) + exchange(n/3/3) + exchange(n/4/3) 
exchange(n/4) = exchange(n/2/4) + exchange(n/3/4) + exchange(n/4/4)

但是，如果不适用，则这些内容将不真实

lli exchange_opt(lli n) 
{
    if (n >= 12 * 4) // for n=48+ none of the terms would trigger n < 12
    {
        lli sum = 0;
        sum += exchange_opt(n / 4);
        sum += exchange_opt(n / 6) * 2;
        sum += exchange_opt(n / 8) * 2;
        sum += exchange_opt(n / 9);
        sum += exchange_opt(n / 12) * 2;
        sum += exchange_opt(n / 16);
        return sum;
    }
    if (n > 11)
    {
        lli sum = 0;
        sum += exchange_opt(n / 2);
        sum += exchange_opt(n / 3);
        sum += exchange_opt(n / 4);
        return sum;
    }
    return n;
}

在我的机器上，这比默认实现快4倍，而且这个想法是可扩展的，例如，您可以展开三个级别的递归，但可以增加其应用的n计数。这是一个版本，它从基本情况展开了三个层次的递归，并结合了类似的术语来减少函数调用。现在速度快了8倍：

lli exchange_opt(lli n) 
{
    if (n >= 12 * 4 * 4)
        // for n=48+ none of the core terms would trigger n < 12
    {
        lli sum = 0;
        sum += exchange_opt(n / 8);
        sum += exchange_opt(n / 12) * 3;
        sum += exchange_opt(n / 16) * 3;
        sum += exchange_opt(n / 18) * 3;
        sum += exchange_opt(n / 24) * 6;
        sum += exchange_opt(n / 27);
        sum += exchange_opt(n / 32) * 3;
        sum += exchange_opt(n / 36) * 3;
        sum += exchange_opt(n / 48) * 3;
        sum += exchange_opt(n / 64);
        return sum;
    }
    if (n >= 12 * 4)
    // for n=48+ none of the core terms would trigger n < 12
    {
        lli sum = 0;
        sum += exchange_opt(n / 4);
        sum += exchange_opt(n / 6) * 2;
        sum += exchange_opt(n / 8) * 2;
        sum += exchange_opt(n / 9);
        sum += exchange_opt(n / 12) * 2;
        sum += exchange_opt(n / 16);
        return sum;
    }
    if (n >= 12)
    {
        lli sum = 0;
        sum += exchange_opt(n / 2);
        sum += exchange_opt(n / 3);
        sum += exchange_opt(n / 4);
        return sum;
    }
    return n;
}

顺便说一句，为了测试，我运行了0。。。9999，然后将OP的原始函数和my函数的时间相加，同时测试结果是否相等。由于这是针对大量数据进行优化的，因此对于非常大的数据，结果可能会更好。

我猜测，展开的每一级递归都将使该算法的速度大约翻倍。与其像我这样手工计算展开，实际上可以编写一个程序，输出所需展开级别的正确方程式。基本上是在最短的时间内计算交换（n），您希望展开到最接近的递归级别“k”，其中n

但是手动展开循环已经足够了。这是一个递归函数，它生成递归函数到任何需要展开的级别。它使用std::向量，std::map，所以你需要包含正确的标题：

std::vector<std::map<lli, lli>> map1;
map1.push_back(std::map<lli, lli>());
map1[0][2] = 1;
map1[0][3] = 1;
map1[0][4] = 1;
const int unrolled_levels = 20;
for (int level = 1; level < unrolled_levels; ++level)
{
    map1.push_back(std::map<lli, lli>());
    for (auto i = map1[level - 1].begin(); i != map1[level - 1].end(); ++i)
    {
        map1[level][(*i).first * 2] += map1[level - 1][(*i).first];
        map1[level][(*i).first * 3] += map1[level - 1][(*i).first];
        map1[level][(*i).first * 4] += map1[level - 1][(*i).first];
    }
}

int level = unrolled_levels - 1;
std::cout << "\tlli exchange_opt(lli n) // unroll" << level << "\n\t{\n\n";
for (int inner_level = level; inner_level >= 0; --inner_level)
{
    lli mult = 12;
    std::cout << "\t\tif (n >= 12LL ";
    for (auto i = 0; i < inner_level; ++i)
    {
        std::cout << " * 4LL";
        mult *= 4LL;
    }
    std::cout << ") // " << (mult) << "\n\t\t{\n";
    std::cout << "\t\t\tlli sum = 0;\n";

    for (auto i = map1[inner_level].begin(); i != map1[inner_level].end(); ++i)
    {
        std::cout << "\t\t\tsum += exchange_opt(n/" << (*i).first << "LL)";
        if ((*i).second > 1) std::cout << " * " << (*i).second;
        std::cout <<"; \n";
    }
    std::cout << "\t\t\treturn sum;\n";

    std::cout << "\t\t}\n";
}
std::cout << "\t\treturn n;\n";
std::cout << "\n\t}\n\n";

基本上，您可以将unrolled\u levels设置为您想要的任何级别。每一级展开4倍大数字的等式。请注意，输出函数将是巨大的，它测试n的数字范围，然后继续尽可能地短路子级别。对于一些更高的数字，它计算出一个部分值，并乘以数千或数百万，有效地缩短了数百万个函数调用。

复制并粘贴此代码的输出，并将其用作计算exchange（n）的函数。对于100万左右的数字，它比原始公式快200倍（运行时间的0.5%）。对于1亿左右的数字，只需要原始方程式的1%的1/70，速度快了7000倍。

顺便说一句，这可能更快。我没有在同一个分支中遍历并收集乘以相似常数的项。