Может bigO алгоритма быть найденным программно путем анализа его perfs?
Обратите внимание, что у меня нет "проблемы", и я не ищу "другой способ найти большой O моего алгоритма".
То, что я хотел бы знать, - то, если бы это была бы возможная запись программа, которой Вы передали бы точки данных, которые все будут perfs измерениями алгоритма для различного входного размера: (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! алгоритм?
5 ответов
Вы ищете Аппроксимацию кривой . Все известные мне простые алгоритмы для решения этой проблемы будут пытаться уместить точки данных в какой-то полином, но я подозреваю, что есть такие, которые также смогут различать полиномы и неполиномы.
Вы можете использовать аппроксимацию кривой (см. @Max S.) для определения формулы, описывающей ваши данные. Однако это только половина дела, поскольку невозможно узнать, полностью ли описывают данные ваш алгоритм.
Например, ваш алгоритм может представить линейное поведение для n <1 000 000 000, а затем начать вести себя квадратично. Если у вас нет точки данных, где n> 1 000 000 000, ваша программа анализа не сможет дать вам правильный ответ.
Таким образом, вы можете сделать это программно, но результаты будут ограничены точками данных в вашем образце. И нет никакого алгоритмического способа определить, достаточно ли выборка охватывает все "интересные" точки.
Если вы пытаетесь оценить big-O эмпирически, вы должны быть очень осторожны, чтобы убедиться, что вы тестируете на широком диапазоне экземпляров в каждом размере. Помните, что big-O - это худший случай . Нередко встречаются алгоритмы, которые хорошо работают почти во всех, за исключением нескольких патологических случаев, но именно эти патологические случаи определяют время big-O. То есть, если вы пропустите патологические случаи в своей выборке, вы можете отказаться от идеи, что алгоритм O(2^n) - это O(n).
Если вам действительно нужно большое время О, а не просто идея средней производительности, то я рекомендую доказать это аналитически. Не сделав этого, вы не можете быть уверены, что не пропустили какой-то патологический вход.
Я думаю, вы могли бы аппроксимировать это с помощью регрессии, но не получить точных результатов. Это потому, что большинство алгоритмов имеют разную производительность в зависимости от входных данных (а не только от размера). Итак, чтобы понять это полностью, вам понадобится источник.
Самый большой O предполагает идеализированный машина с бесконечной памятью с одинаковым временем доступа, без влияния других приложений и т.д. Итак, вы определяете, как алгоритм работает в реальном мире, а не в его идеализированной среде выполнения.