Можно ли программно найти большую часть алгоритма, проанализировав его характеристики?

Question

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

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

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

    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?

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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