2016-03-01 153 views
0

我試圖解決這個遞歸:解決遞歸T(N)=日誌(T(N-1))+ 1

      T(n)=log(T(n-1))+1 :n>2 
          T(n)=O(1)    :n=2 

我得到O(1)的答案,但我覺得我錯過了一些東西。

我很樂意獲得一些幫助。

在此先感謝!

+1

'n'有什麼限制嗎? 「0」還是什麼?你的代碼在哪裏? –

+0

謝謝我編輯了這篇文章。 –

+0

你現在還不清楚你在問什麼。沒有代碼表明你甚至在嘗試! 'T(n)= O(1):n = 2'那是什麼? 'T(2)= O(1)'什麼? –

回答

2

你的遞推關係收斂至1.0的任何值> = 1.0

你的答案Ô(1)是相當正確的。遞歸關係可以用這種簡單的方式表達出來,而不是被賦予算法嗎?


讓我再試一次。另外,也許我們都有點困惑。我在單一電話層面回答;也許你需要整體的答案(更可能的是,現在我想到了)。

首先,讓我們來一個電話。如果n = 2,那是恆定的時間。如果n> 2 ...這是我對符號不太熟悉的地方。這是表示調用單個的時間,還是表示整個遞歸序列降至n = 2?由於實際考慮,我認爲它必須針對單個呼叫。這使我以前的答案不正確。

看看n = 3的呼叫。此膨脹並解決了作爲

T(3) = log(T(2)) + 1 
T(3) = log(1) + 1 
T(3) = 0 + 1 = 1 

通過感應T(N)= 1對於n> = 2。事實證明,即使基礎案例 - T(2) - 具有除1以外的值,只要它是有限的並且超過1 /(無論我們用於日誌的基礎是什麼),該系列將會收斂到1,並且每個呼叫將保持不變。因此,要解決T(n),我們有n-2個調用,每個調用都是T(1)。這給出了總體複雜度爲O(n)

更清楚了嗎?

+0

非常感謝您的回答。儘管如此,解決方案對我來說依然沒有意義。 –

+0

非常感謝您的擴展。根據你的解釋,我通過歸納瞭解到:如果T(n-1)= 1,那麼: T(n)= log(T(n-1))+ 1 = log(1)+1 = 1。所以T(n)= O(1)。 這似乎不適合我。當c是某個常數時,T(n-1)= c,並且然後:T(n)= log(T(n-1)+1 = log(c)+1 其不等於O (1)? –

相關問題