Может ли алгоритм BigO алгоритма быть найден программным путем, анализируя его perfs?

Обратите внимание, что у меня нет "проблемы", и я не ищу "другого способа найти большой O моего алгоритма".

То, что я хотел бы знать, это то, что можно было бы написать программу, на которую вы передавали бы точки данных, которые все будут выполнять измерения алгоритма для различных размеров ввода: (n,time taken to solve problem for n), и это будет определять сложность вашего алгоритма.

Например, здесь может быть вход (он может быть намного больше, это просто пример, а не вопрос):

    36 000 took 16 ms
   109 000 took 21 ms
   327 000 took 68 ms
   984 000 took 224 ms
 2 952 000 took 760 ms
 8 857 000 took 2305 ms
26 571 000 took 7379 ms
79 716 000 took 23336 ms

Используя такой тип данных, можно ли написать программу, которая сообщила бы, если у нас есть, скажем, O(n), log(n), n log(n) или n! algo?

Ответ 1

То, что вы ищете, это Настройка кривой. Все простые алгоритмы для этой проблемы, о которых я знаю, будут пытаться сопоставить точки данных с каким-то многочленом, но я подозреваю, что есть те, которые могут также различать полиномы и неполиномы.

Ответ 2

Вы можете использовать подгонку кривой (см. @Max S.) для определения формулы, которая описывает ваши данные. Тем не менее, это только половина истории, так как нет никакого способа узнать, полностью ли данные описывают ваш алгоритм.

Например, ваш алгоритм может представить линейное поведение для n < 1 000 000 000, а затем начинают вести себя квадратично. Если у вас нет данных, где n > 1,000,000,000, то ваша программа анализа не сможет дать вам правильный ответ.

Таким образом, в заключение вы можете сделать это программно, но результаты будут ограничены точками данных в вашем примере. И нет алгоритмического способа определить, достаточно ли в выборке покрывает все "интересные" точки.

Ответ 3

Если вы пытаетесь оценить большой-O эмпирически, вы должны быть очень осторожны, чтобы убедиться, что вы тестируете в широком диапазоне экземпляров при каждом размере. Помните, что big-O - это понятие наихудшего. Нередко можно найти алгоритмы, которые хорошо работают почти во всех случаях, кроме нескольких патологических случаев, но именно эти патологические случаи определяют время большого О. То есть, если вы пропустите патологические случаи в вашей выборке, вы можете отказаться от идеи, что O (2 ^ n) алгоритм O (n).

Если вам действительно нужно большое время O, а не просто идея средней производительности, я рекомендую проверить его аналитически. Не делая этого, вы не можете быть уверены, что не пропустили какой-либо патологический ввод.

Ответ 4

Я думаю, вы могли бы аппроксимировать его с помощью регрессий, но не получить точные результаты. Это потому, что большинство алгоритмов имеют разную производительность в зависимости от того, какой вход (а не только размер). Чтобы понять это полностью, вам понадобится источник.

Ответ 5

Самый большой вариант - идеальная машина с бесконечной памятью с равномерным временем доступа, без влияния других приложений и т.д. Особенно, когда вы переходите на пороговые значения, такие как размеры кеша, размеры основной памяти (подкачки в/из файла подкачки ) может оказать существенное влияние на производительность. Итак, вы определяете, как работает алгоритм в реальном мире, а не идеализированная среда выполнения.