function - 给定这组点，这个和 Big(O) 符号的数学函数是什么？

Question

X=2, y=1
X=3, y=3
X=4, y= 6
X=5, y= 10
X=6, y= 15
X=7, y= 21
X=8, y=28

我知道 f(x) = f(x-1) + (x-1)

但是......这是正确的数学函数吗？大 O 符号是什么？

score 2 · Accepted Answer

2

正确的（或至少比递归更有效）方程将是

f(x) = x * (x - 1) / 2

于 2011-06-17T01:10:24.240 回答

score 0 · Accepted Answer

~~看起来像家庭作业。你应该用作业标签来标记它。~~

你的意思是 f(x) = f(x-1) + (x-1) 吗？

score 0 · Accepted Answer

是的，函数是正确的，y 值之间的差值递增 1

编辑：感谢真实性的评论

对于函数的复杂性，您可以像这样看到 y

y= 1 + (1+2) + (1+2+3) + ....(1+2+3+..n)

作为最高可能的程度项 1+2+3...n 是 O(n^2) y=O(n^2)

score 0 · Accepted Answer

正确陈述问题的方法是：

f(x) = f(x - 1) + (x - 1)
f(1) = 0

您想f(x)根据x.

有很多方法可以解决这些递归公式。我喜欢使用 Wolfram Alpha，它有一个简单的界面。

这给了你准确的答案，用大 O 表示法你会说函数f在O(x^2).

4 回答 4