Как определить функцию по значениям пар y;x?

Question

[Максим]

Можно ли как-то математически определить, что за функция (линейная, логарифмическая и тд) если известно сколько-нибудь пар (допустим более двух) ее значений y;x?

Comments

[eegmak]

посмотрите wolfram mathematica, наверное у них есть и api для доступа через ваше ПО.

Answer 1

[kalapanga]

Например так, как реализовано здесь: https://planetcalc.ru/5992/
Только учтите, что многие наборы данных могут одновременно одинаково хорошо (или одинаково плохо) описываться функциями разного вида.

Comments

[Максим]

Спасибо! На самом деле я учусь определять сложность алгоритма через О нотацию.
Пробую на алгоритме сортировки который я сам написал. Он наверное похож на MergeSort.
Но я не понимаю как иногда точно определить сложность. В моей ситуации, подходят и линейная и степенная и кубическая функции.
И какую тогда сложность алгоритму ставить..

[Rsa97]

Максим, Сложность алгоритма определяют аналитически, а не замерами времени работы программы.

[Максим]

Rsa97, Кто сказал, что я замеряю время работы программы? Я измерил и знаю кол-во итераций при разной длине массива. Если быть точным, то в моей ситуации формула кол-ва итераций будет 2,5*n*n/10.
Где n - длина массива. Это какая сложность будет? Допустим 2,5 можно отбросить, остается n* n/10.
n/10 тоже можно отбросить, так как n/10 меньше чем n в 10 раз, а значит уже не имеет значения.
Правильный ответ это O(n) ?

[Rsa97]

Максим, Если это сортировка, то количество итераций, как правило, зависит от степени начальной сортированности данных. Для массива, уже отсортированного в нужном порядке и массива того же размера, но отсортированного в обратном порядке, вы можете получить совершенно разные результаты.

[Максим]

Rsa97, Это я знаю! Сейчас это не имеет значения. Массивы которые я прогоняю двух уровней сложности. Один рандомный - числа будут распределены случайно - это значит уже при 100 генерациях массива мы получим весьма усредненный результат. А второй вариант сложности это когда массив отсортирован в обратном порядке, и в этом случае будет максимальное кол-во итераций, и влиять будет только длина массива.
Я хочу определить сложность с помощью большой О нотации. Именно эту тему я хочу понять. Если вы можете помочь, помогите пожалуйста, объясните.

[Rsa97]

Максим, Повторю, O-нотацию получают анализируя сам алгоритм. Для общих алгоритмов сортировки наилучшим результатом будет O(n*logn). Для частных случаев можно получить O(n).
Любые замеры вам дадут только гипотезу, чтобы утверждать, что ваш алгоритм имеет конкретную сложность, всё равно придётся расписать её аналитически.

[Максим]

Rsa97, Хорошо, спасибо! Вы можете тогда сказать, как это сделать? Я имею ввиду, какие разделы аналитики я должен почитать, посмотреть. Может быть какой-то конкретный аналитический инструмент/прием подходит для этой задачи? Я хотя бы посмотрю на сложность этой темы.

[Rsa97]

2,5*n*n/10 => O(n²)
Отбрасываются коэффициенты и слагаемые с младшими степенями.

[Максим]

Понял, спасибо. Эту бредятину про "более чем в 2 раза меньше..." я услышал в одном поучительном видео на Youtube.

Answer 2

[Михаил]

Кто сказал, что я замеряю время работы программы? Я измерил и знаю кол-во итераций при разной длине массива. Если быть точным, то в моей ситуации формула кол-ва итераций будет 2,5*n*n/10.
Где n - длина массива. Это какая сложность будет? Допустим 2,5 можно отбросить, остается n* n/10.
n/10 тоже можно отбросить, так как n/10 меньше чем n в 10 раз, а значит уже не имеет значения.
Правильный ответ это O(n) ?

O(n) - неправильный ответ
Если 2.5*n*n/10 - точная формула тогда надо писать следующим образом
2.5*N^2/10 = 2.5/10 * N^2 => O(N^2)

Comments

[Максим]

Благодарю! Только я не понял, почему мы отбрасываем n/10. Ведь n/10 это уже в 10 раз меньше n.
Если одно n меньше другого n более чем в 2 раза, то оно становится незначительным. Разве не так? Или скажите пожалуйста, что я неверно понимаю?

[Михаил]

меньше n. Если одно n меньше другого n более чем в 2 раза,

Конечно нет. Этот же пример но по Вашей логике
2.5*n*n/10 = 2.5* (n/2) * (n/5)
2.5- опускаем
n/2 - опускаем т.к. меньше чем 2 раза
n/5 - опускаем т.к. меньше чем 2 раза
Итого получается O(1) или даже O(0) - что какбы вообще далеко от правды.

Логика следующая

Упрощаем выражение и как сложность берем самую большую степень
Пример
- 2.5*N^2/10 + 6*N => O(N^2)
- 2.5*N^2/10 + 100500*N => O(N^2)
- 0.0000001*N^2/10 + 6*N => O(N^2)
2.5*N*Log(N/2) + 6*N => O(N*Log(N))

[Максим]

Михаил, Правильно ли я понял, что есть одно правило, это оставить n самой старшей степени?

Answer 3

[Александр Скуснов]

По-моему, проще нейронную сеть настроить. Вам даже не надо будет искать названия вашего базиса функций, она вам просто будет давать численный ответ.

Answer 4

[mayton2019]

Скорее всего ответов будет много.

Если скопление точек - похоже на "рога" на плоскости то под функцию одинаково подходит и косинус, и парабола и гиперболический косинус.

И здесь очень важно понять что четкого ответа не будет.