0
我已經編寫了一個方法的僞代碼來計算Pascal三角形第i行中的一個入口。遞歸方法的運行時間
Pascal(i,j)
if(i==j or j==0)
return 1;
return Pascal(i-1,j-1) + Pascal(i-1,j)
我的問題是,我無法弄清楚運行時間。我知道它是指數型的,但我不知道如何通過求解一個遞推關係來證明它。
我已經編寫了一個方法的僞代碼來計算Pascal三角形第i行中的一個入口。遞歸方法的運行時間
Pascal(i,j)
if(i==j or j==0)
return 1;
return Pascal(i-1,j-1) + Pascal(i-1,j)
我的問題是,我無法弄清楚運行時間。我知道它是指數型的,但我不知道如何通過求解一個遞推關係來證明它。
你會做好一些例子,看看你有多遠。請記住,你有一個三角形。你從第i行開始,然後你在第i-1行。下一步,你在第i-2行。等等,在最壞的情況下,你要走多少行?
繪製圖片並做實例來建立直覺。從i = 6的幾個例子中找到一個證明應該很容易。
我這樣做了,在我看來,要獲得第n行的值需要在前一行加上n-1的數量。所以,我得到T(n)= T(n-1)+ n-1。它是否正確? – user1317750 2013-05-01 12:34:54
看起來您可能在代碼中存在一些錯誤:在if中,您將j設置爲0,而不是使用'=='。此外,你只返回1 - 如果我!= 0和j!= 0,返回哪裏? – 2013-05-01 03:41:05
我建議在MathOverflow詢問你的問題 – 2013-05-01 08:35:45