如何優化方法

我一直在解決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

謝謝你的建議:)。是的，我當然可以做這件事:) –

如何優化方法

回答

相關問題