寫函數的遞推關係

Question

我知道遞歸關係的公式是T（n）= aT（n/b）+ f（n）。考慮到這個等式，我知道如何解決BigO。我的家庭作業問題要求我編寫一個遞歸函數來計算列表中的節點數，我做了，但後來要求我編寫一個遞歸關係。這裏是我的代碼：

int count(ListNode *l) 
{ 
    if(!l) return 0; 
    if(!l->next) return 1; 

    return 1 + count(l->getNext()); 
} 

但我完全失去了關於如何創建/制定自己的遞推關係式...我怎麼找a或b ....我不知道從哪裏開始。我如何編寫此函數的遞歸關係？謝謝。

Answer 1

我從來沒有一直在寫長期復發關係，但這應該是答案： T（n）= T（n-1）+ CONSTANT。你的公式是：T（n）= aT（n/b）+ f（n）。 b：你把問題分成b個部分。 f（n）：是用多少時間來解決問題 a：問題實例的數量 在你的問題 你可以線性地將問題減少1，所以它是n-1。常數意味着它需要一些恆定的時間來解決問題

PS：我沒有使用8年的遞歸關係，但事實如此。

Answer 2

您的第一個遞歸關係通常用於描述運算時間爲分而治之算法。 a此處顯示您將數據劃分爲多少個零件，1/b顯示每個零件中使用的原始數據，f(n)顯示您在每個「等級」上需要多少時間。例如，在QuickSort算法中，您將數據（數組或列表）分成兩部分，每部分只是原始數據的一半（1/2），並且在每個劃分的「級別」上，您都需要遍歷所有的元素1次。所以遞推關係是

T(n) = 2T(n/2) + n 

（計算結果爲O（N * LG電子（n））的） 並在每一個「級別，你將數據分成兩個部分，但只取其中1二進制搜索，和時間「是不變的，所以關係是：

T(n) = T(n/2) + 1 

但是，你的C函數並不遵循分而治之的策略。相反，它演示了數學歸納。您可以定義開始條件：如果l等於NULL，則長度爲0，如果它l->next等於NULL（您還定義了列表中1個元素的條件）。然後定義一種歸納步驟 - 如果知道第（n-1）個元素的函數值，則定義如何計算第n個元素的函數。因此，知道第一個元素的函數的值，可以應用此規則並獲得第二個元素的值，然後獲得第三個元素的值等等。

所以你可以看到歸納法是由自然界的遞推算法。這裏我們有2次考慮。首先是在起點（或終點 - 它取決於您查看列表的順序）計算值的時間。在你的函數中你只是返回這個值，所以它是不變的（C1）。其次是做出1步的時間。在你的功能也是不變的（C2）。直覺上，你應該可以看到這個算法的執行時間爲：

T(n) = C1, when n = 1 
T(n) = T(n - 1) + C2, when n > 1 

因此，除非n = 1，你定義的時間，通過時間來執行它n - 1元素n元素上執行算法。在比戈符號任何常數定義爲1和1個元件的情況下，不考慮，所以最終遞推關係是：

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

（其計算爲T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n，或O(n)）

進一步閱讀：

• Introduction to Algorithms Thomas H. Cormen。
• Art of Computer Programming Donald Knuth。