帕斯卡公式的复杂性

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/