2013-05-01 55 views
0

我已經編寫了一個方法的僞代碼來計算Pascal三角形第i行中的一個入口。遞歸方法的運行時間

Pascal(i,j) 
    if(i==j or j==0) 
    return 1; 
    return Pascal(i-1,j-1) + Pascal(i-1,j) 

我的問題是,我無法弄清楚運行時間。我知道它是指數型的,但我不知道如何通過求解一個遞推關係來證明它。

+0

看起來您可能在代碼中存在一些錯誤:在if中,您將j設置爲0,而不是使用'=='。此外,你只返回1 - 如果我!= 0和j!= 0,返回哪裏? – 2013-05-01 03:41:05

+1

我建議在MathOverflow詢問你的問題 – 2013-05-01 08:35:45

回答

0

你會做好一些例子,看看你有多遠。請記住,你有一個三角形。你從第i行開始,然後你在第i-1行。下一步,你在第i-2行。等等,在最壞的情況下,你要走多少行?

繪製圖片並做實例來建立直覺。從i = 6的幾個例子中找到一個證明應該很容易。

+0

我這樣做了,在我看來,要獲得第n行的值需要在前一行加上n-1的數量。所以,我得到T(n)= T(n-1)+ n-1。它是否正確? – user1317750 2013-05-01 12:34:54