帕斯卡公式的複雜性

Question

我已經看到了這個問題，我無法解決它 問題是找到C（m，n）= C（m-1，n-1）+ C（m，n -1）（帕斯卡公式） 它是一個迭代公式，但有兩個變量，我不知道要解決這個問題 我會很樂意爲您提供幫助...... :)

Answer 1

如果您考慮此公式的2D表示當給定「高度」時，你可以對數字進行求和以涵蓋三角形的「面積」，所以如果直接從公式計算複雜度將是o（n^2）。

Idk如果我剛纔所說的話對你來說有意義，但你也可以考慮表達固定n的公式的每次迭代的複雜性，這會給你線性複雜度，乘以n上的線性複雜度你仍然應該得到O（N^2）

這一思路似乎符合他們這裏展示：

http://www.geeksforgeeks.org/pascal-triangle/