遞推公式

Question

首先，是它的硬件 - 真的盡力了，但不知道的東西，所以生病很高興，如果你能幫助我:)

我有這樣的代碼：

我需要給這個編碼一個recusive公式。 我做的是 - 第一次遞歸調用是T（n/2）。 第二 - 這是問題！真的很混淆，加上'p'...是那個 T（n/2）呢？ 三 - 對THETA運行（N） 和外面遞歸調用是T（N）...

你能幫我到最後的公式？

感謝

Answer 1

如果我正確地閱讀它，您希望重現運行時複雜性。

對於n > 1，你有復發參數floor(n/2)與參數n-floor(n/2)，之後你輸出n項目。因此你有

T(n) = T(cost of first recursive call) + T(second rec. call) + extra work 

你現在應該帶入一個適用於主定理的形式。

Answer 2

這可能是一個有趣的問題或者您誤解了問題。你有什麼是一個遞歸公式。你需要將這個公式從C++切換到更傳統的數學符號嗎？需要找到一個非遞歸算法？在你回答這個問題時，T是什麼？術語公式在這裏並不適用，因爲沒有任何東西被計算出來。這是一個永不修改給定數組的無效函數。發生的所有事情都是按照某種順序將數組中的某些元素放到屏幕上的。

我會從追蹤示例開始，瞭解發生了什麼。 比方說A = {1,2,3,4}然後「FUNC（A，0,4）」是：

tracing func(A,0,4) : 
p = 2 
func(A,0,2) 
func(A,2,2) 
cout << 1 2 3 4 

tracing func(A,0,2) : 
p = 1 //start=0; n=2 
func(A,0,1) 
func(A,1,1) 
cout << 1 2 

tracing func(A,2,2) : 
p = 1 //start=2; n=2 
func(A,2,1) 
func(A,3,1) 
cout << 3 4 

tracing func(A,2,1) : 
p = 0 //start=0; n=1 
func(A,0,0) 
func(A,0,1) 
cout << 1 

tracing func(A,3,1) : 
p = 0 //start=3; n=1 
func(A,3,0) 
func(A,3,1) 
cout << 3 

tracing func(A,2,1) : 
p = 0 //start=0; n=1 
func(A,0,0) 
func(A,0,1) 
cout << 1 

在這一點上，我要停下來，因爲這是你的家庭作業的問題。你可以從這裏完成它。