如何优化方法

我一直在解决hackerrank中的问题。我相信我的解决方案是正确的，但随着输入矩阵变大，程序因超时而终止。如何优化方法

我有一个方法，我在下面找到一个系列。此方法获取数组索引号并基于该方法计算一个数字。基于这个数字，我用一些东西来填充我的数组。但程序每次都会终止。它只适用于最大n = 2。我认为这种方法应该进行优化，因为它对大n使用巨大的递归。有什么建议我应该怎么做？

static int hacko(int n) 
{ 
    if(n==1) 
     return 1; 
    else if(n==2) 
     return 2; 
    else if(n==3) 
     return 3; 
    else 
    return hacko(n-1)+(2*hacko(n-2))+(3*hacko(n-3)); 

}

来源

2016-12-24 Nazmus Salehin

递归对于大'n'很重。递归是你的任务的一个要求吗？ – thatguy

不需要。我想使用任何东西，如果可行的话。 –

你可能避免不必要的分支，这可能是昂贵的，就像这样：

static int hacko(int n) { 

    if(n < 4) 
     return n; 
    else 
     return hacko(n-1)+(2*hacko(n-2))+(3*hacko(n-3)); 

}

我认为n > 0，否则使用if(n > 0 && n < 4)。但是，您声明：

它只适用于最大n = 2。

所以您发布的方法是最有可能不是瓶颈，因为n=3相比n=1或n=2不添加任何显著复杂的代码。或者你是什么意思？

由于递归是不是对你的要求，你可以做以下的迭代方法：

static int hacko(int n) { 

    // Shortcut for n=1, n=2 and n=3 
    if (n < 4) 
     return n; 

    // Array to store the previous results 
    int[] temp = new int[n]; 
    temp[0] = 1; 
    temp[1] = 2; 
    temp[2] = 3; 

    // Iterative approach, more scalable, counts up 
    for (int i = 3; i < n; i++) { 
     temp[i] = 3 * temp[i - 3] + 2 * temp[i - 2] + temp[i - 1]; 
    } 

    return temp[n - 1]; 

}

来源

2016-12-24 19:08:45 thatguy

谢谢。这应该会降低一些复杂性 –

添加了迭代解决方案，因为您声明递归不是必需的。 – thatguy

Omg！这很好。非常感谢你。你把一个丑陋的递归转变为一个简单的迭代:) –

这里的问题是，对于n值很大，它计算hacko（N-1）+（2 * hacko（n-2））+（3 * hacko（n-3））递归。这可能是耗时且不必要的。

您可以通过将hackos（i）的值保存在数组中并获取hacko（n-1）+（2 * hacko（n-2））+（3 * hacko（n-3））），而不是每次递归计算。 ü需要从i开始循环= 1到i = N

例：

int savedData[] = new int[N]; 
static int hacko(int n) 
{ 
    if(n==1) 
     return 1; 
    else if(n==2) 
     return 2; 
    else if(n==3) 
     return 3; 
    else 
    return savedData[n-1]+(2*savedData[n-2])+(3*savedData[n-3]); 

} 

for(int i=1;i<N;i++) { 
savedData[i] = hacko(i); 
}

希望它帮助。

来源

2016-12-24 19:17:37

谢谢你的建议:)。是的，我当然可以做这件事:) –

如何优化方法

回答

相关问题