如何編寫僞代碼的遞歸關係？

Foo(A,f,l) 
**Precondition: A[f ...l] is an array of integers, f,l are two naturals ≥ 1 with f ≤ l. 
if (f = l) then 
    return A[f] 
else 
    m ← floor of((f+l)/2) 
    return min(Foo(A,f,m), Foo(A,m + 1,l)) 
end if

糾正我，如果我錯了，但我認爲這段代碼返回數組的最小整數。但是，我怎樣才能找出用陣列A描述時間複雜性的遞歸關係？你能指導我解決方案，以便我能理解嗎？我甚至不知道從哪裏開始。如何編寫僞代碼的遞歸關係？

來源

2016-09-24 LeBlanc

取A，f，l的一些示例值並畫出所做的調用，即完全重複。你會看到在每次通過時，搜索空間減半。複雜性是對數的。 – Rishav

有了這個前提'f <='，你不能確保它在你的內部調用中實現。此外，它似乎是一個無用的先決條件，也許你應該刪除它。你既不能確保'm> = 1' –

看看這個[問題]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） – DarthRubik

我們可以從僞代碼的結構中恢復的遞歸關係。我們可以讓T(n)表示算法所用的時間作爲輸入大小的函數。對於n = 1，時間是不變的，比如T(1) = a。我們現在的問題是針對較大的n，我們如何表達T(n)？

我們將在n > 1的else子句中。我們做一些額外的工作 - 我們稱之爲b - 然後調用函數兩次，一次輸入大小爲floor(n/2)的輸入，一次輸入大小爲ceiling(n/2)的輸入。所以我們可以把這部分遞歸寫成T(n) = b + T(floor(n/2)) + T(ceiling(n/2))。現在我們可以寫出一些條款。

n T(n) 
1 a 
2 b + a + a = b + 2a 
3 b + b + 2a + a = 2b + 3a 
4 b + b + 2a + b + 2a = 3b + 4a 
5 b + b + 2a + 2b + 3a = 4b + 5a 
... ... 
k = (k-1)b + (k)a = kb - b + ka = k(a + b) - b

我們發現猜測，T(n) = (a + b)n - b一些常量a和b這取決於工作的大量的成本，我們可能需要爲常數（注意，計算(f + l)/2是不是在n方面確實不變，但會不要改變我們的分析）。我們可以用數學證明來證明這一點：

T(1) = a = (a + b)(1) - b是對的;
假定所有n <= k的T(n) = (a + b)n - b。
請問T(k + 1) = (a + b)(k + 1) - b是否持有？請記住T(k + 1) = b + T(floor((k+1)/2)) + T(ceiling((k+1)/2)。假設k+1是偶數，並且m = (k+1)/2。然後T（k + 1）= b + 2T（m）= b + 2 [（a + b）（m）-b] = b + 2（m）（a + b）-2b =（2m） + b） - b =（k + 1）（a + b） - b , as required. The case where k + 1`是奇數剩下作爲練習。

這是線性的。

來源

2016-09-26 17:19:07 Patrick87

-1

你說得對。它返回數組的最小整數。

而且複雜

O(nlog(n)); n = size of the array

Explanation:在每個呼叫，你打破的數組，調用多達f=l相等的兩個部分。它爲數組中的每個數字調用函數O(log(n))次。因此，總複雜度爲O(nlog(n))

來源

2016-09-25 05:24:46 jbsu32

如何編寫僞代碼的遞歸關係？

回答

相關問題