時間複雜度和遞推關係

我有困難，瞭解如何開發遞推關係。我給出的代碼是時間複雜度和遞推關係

int result = bizarre(n, n); 
public static int bizarre (int first, int second) 
{ 
    if (second <= 1) 
    { 
    int temp = 0; 
    for (int i = 0; i < first; i++) 
     temp += i; 
    return temp; 
    } 
    return bizarre (first, second-1); 
}

從什麼，我的理解是，

T(n) = n + 1 
T(1) = 1

，但似乎並不正確。有人可以幫我嗎？

來源

2017-10-20 Saff

我想你遇到麻煩在這裏的原因之一是，有兩個獨立的參數的功能，讓你的遞推關係需要有兩個不同的參數考慮到這一點。

在你的第二個參數是0或1的情況下，你做的工作成正比的第一個參數。你可以寫成：

T（m，1）= Θ（m）。

否則，該函數執行恆定的工作量，然後對相同的第一個輸入和遞減的第二個輸入進行遞歸調用。這看起來如下：

T（m，n）= T（m，n-1）+ O（1）。

你認爲你可以從那裏解決的事情？

來源

2017-10-21 00:18:34 templatetypedef

呀，這兩個參數確實讓我困惑，我不知道在這樣的關係是否還是不寫會工作。我明白你是如何得到經常性案件的，但你能否解釋基本案例？我似乎無法把頭圍住它。另外，你將如何去獲得時間複雜性？我沒有做過類似的問題，所以我很抱歉，如果這對我來說應該很簡單。 – Saff

在基本情況下，你只需要一個運行「第一次」的循環，每個都做O（1）。我用* m *表示你的第一個參數，所以完成的工作是O（m）。 – templatetypedef

謝謝，這清除了它。最後這給了我一些混亂的一個問題是第一行，其中爲奇異的參數均爲「N」，就這並不意味着第一和第二是導致基礎情況爲T（1,1）= O（相同的值1）？ – Saff

一般而言，復發關係由

T(n) = no. of subproblems generated at each step * T(size of each subproblem) + complexity of the divide/conquer step

和

T(1) = complexity of base case(s)

給出。在您的示例中，變量「第二」在每個遞歸調用越來越小1。此外，您在每個步驟中創建的子問題數量僅爲一個，因爲您只需調用一次該方法。

的代碼並沒有真正做任何工作，在除了比較各遞歸步驟，所以這是一個O（1）操作。

所以，

T(n) = T(n - 1) + O(1)

最後，T（1）是在基情況下，它是n個數字的總和會發生什麼。

T(1) = O(n)

來源

2017-10-20 23:59:41 omijn

時間複雜度和遞推關係

回答

相關問題