Учитывая этот набор точек, какова будет математическая функция для этого и обозначения 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?

Answer 1

Правильное (или, по крайней мере, значительно более эффективное, чем рекурсивное) уравнение будет

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

Answer 2

Способ правильно сформулировать проблему:

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

Вы хотите решить f(x) в терминах x.

Существует много способов решения этих видов проблем.рекурсивные формулы.Мне нравится использовать Wolfram Alpha, он имеет простой интерфейс.

Wolfram Alpha запрос "f (x) = f (x-1) + (x-1)"

Это дает вам точный ответ, в нотации big-O вы бы сказали, что функция f находится в O(x^2).

Answer 3

Да, функция верна, разница между значениями 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)

Answer 4

Похоже на домашнюю работу. Вы должны пометить его тегом домашней работы.

Вы имели в виду f (x) = f (x-1) + (x-1)?

Чтобы решить для функции: http://en.wikipedia.org/wiki/Recurrence_relation#Solving

Чтобы получить сложность: http://en.wikipedia.org/wiki/Master_theorem