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)

しかし...それは正しい数学関数ですか? Big O表記は何ですか？

score 2 · Accepted Answer

正しい (または少なくとも、再帰よりもはるかに効率的な) 方程式は次のようになります。

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

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を好んで使用しています。インターフェースが簡単です。

それはあなたに正確な答えを与えます.big-O表記では、関数fはO(x^2).

score 0 · Accepted Answer

~~宿題のようです。宿題タグでマークする必要があります。~~

f(x) = f(x-1) + (x-1) ということですか?

4 に答える 4