Интересно, существует ли какой-либо автоматический способ определения (по крайней мере, грубо) сложной по времени Big-O заданной функции?
Если я нарисую функцию O (n) и функцию O (n lg n), я думаю, что смогу визуально выяснить, что это такое; Я думаю, что должно быть какое-то эвристическое решение, позволяющее сделать это автоматически.
Любые идеи?
Изменить: Я рад найти полуавтоматическое решение, просто задаваясь вопросом, есть ли способ избежать полного ручного анализа.
Похоже на то, что вы просите, это расширение проблемы с остановкой. Я не верю, что такое возможно, даже в теории.
Просто отвечая на вопрос: "Будет ли эта строка кода работать?" было бы очень трудно, если не невозможно сделать в общем случае.
Отредактировано для добавления: Хотя общий случай неразрешимый, см. Здесь частичное решение: http://research.microsoft.com/apps/pubs/default.aspx?id=104919
Кроме того, некоторые из них заявили, что провести анализ вручную - единственный вариант, но я не считаю, что это действительно правильный способ взглянуть на него. Неизбежная проблема по-прежнему неразрешима даже тогда, когда к системе/машине добавляется человек. При дальнейших размышлениях я полагаю, что 99% -ное решение может быть выполнимым и может даже работать так же хорошо, как и лучше человека.
Вы можете запустить алгоритм на разных наборах данных размера, и затем вы можете использовать аппроксимацию кривой, чтобы придумать приближение. (Просто глядя на кривую, которую вы создаете, вероятно, будет достаточно в большинстве случаев, но любой статистический пакет имеет подгонку кривой).
Обратите внимание, что некоторые алгоритмы имеют одну форму с небольшими наборами данных, а другую с большими... и определение больших остается немного туманным. Это означает, что алгоритм с хорошей кривой производительности может иметь столько реальных накладных расходов, что (для небольших наборов данных) он не работает, а также теоретически лучший алгоритм.
Что касается методов проверки кода, то не существует. Но инструмент, позволяющий вашему коду работать на разных длинах и выводить простой файл (RunSize RunLength будет достаточно), должен быть простым. Создание надлежащих тестовых данных может быть более сложным (некоторые алгоритмы работают лучше/хуже с частично упорядоченными данными, поэтому вы хотели бы генерировать данные, которые представляли ваш обычный прецедент).
Из-за проблем с определением "что является большим" и тем фактом, что производительность зависит от данных, я считаю, что статический анализ часто вводит в заблуждение. Оптимизируя производительность и выбор между двумя алгоритмами, реальный мир "каучук попадает в путь" - это единственный окончательный арбитр, которому я доверяю.
Мне любопытно, почему вы хотите это сделать. По моему опыту, когда кто-то говорит: "Я хочу выяснить сложность выполнения этого алгоритма", они не спрашивают, о чем они думают. То, что вы, скорее всего, задаете, - это реалистичная работа такого алгоритма для вероятных данных. Вычисление Big-O функции имеет разумную полезность, но есть так много аспектов, которые могут изменить "реальную производительность выполнения" алгоритма в реальном использовании, что ничто не сравнится с инструментами и тестированием.
Например, следующие алгоритмы имеют один и тот же точный Big-O (wacky pseudocode):
Пример a:
huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
for j = 0; j < foo[j].length, j++
do_something_with foo[i][j]
Пример b:
huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
for i = 0; i < foo[i].length, i++
do_something_with foo[i][j]
Опять же, точно такой же большой-O... но один из них использует порядков строк, и один из них использует порядковый номер столбца. Оказывается, из-за локальности ссылки и когерентности кэша у вас могут быть две совершенно разные фактические исполнения, особенно в зависимости от фактического размера массива foo. Это даже не начинает касаться фактических характеристик производительности того, как работает алгоритм, если он является частью части программного обеспечения, имеющего встроенный concurrency.
Не быть отрицательным nelly, но big-O - это инструмент с узкой областью. Это очень полезно, если вы глубоко внутри алгоритмического анализа или если вы пытаетесь доказать что-то об алгоритме, но если вы занимаетесь коммерческим программированием, доказательство находится в пудинге, и вы захотите иметь фактические показатели производительности принимать интеллектуальные решения.
Ура!
Короткий ответ: это невозможно, потому что константы имеют значение.
Например, я могу написать функцию, которая работает в O((n^3/k) + n^2). Это упрощает до O (n ^ 3), поскольку, поскольку n приближается к бесконечности, член n^3 будет доминировать над функцией, независимо от константы k.
Однако, если k очень велико в приведенной выше примерной функции, функция будет работать почти точно n^2 до некоторой точки пересечения, при которой начнет доминировать термин n^3. Поскольку константа k будет неизвестна любому инструменту профилирования, будет невозможно узнать, насколько большой набор данных для проверки целевой функции. Если k может быть сколь угодно большим, вы не можете создавать тестовые данные для определения времени работы с большим временем работы.
Я удивлен, увидев столько попыток утверждать, что секундомер можно "измерить". Несколько человек дали правильный ответ, но я думаю, что есть еще место для того, чтобы вести основной пункт дома.
Сложность алгоритма не является "программирующим" вопросом; это вопрос "информатики". Ответ на вопрос требует анализа кода с точки зрения математика, так что вычисление сложности Big-O является практически формой математического доказательства. Это требует очень сильного понимания основных компьютерных операций, алгебры, возможно исчисления (пределов) и логики. Никакое количество "тестирования" не может быть заменено на этот процесс.
Проблема с остановкой применяется, поэтому сложность алгоритма принципиально неразрешима машиной.
Пределы автоматизированных инструментов применяются, поэтому можно было бы написать программу для помощи, но она была бы способна чтобы помочь примерно так же, как калькулятор помогает с одной домашней работой по физике, или столько, сколько браузер рефакторинга помогает с реорганизацией базы кода.
Для тех, кто серьезно рассматривает возможность написания такого инструмента, я предлагаю следующее упражнение. Выбирайте достаточно простой алгоритм, такой как ваш любимый сорт, как ваш субъектный алгоритм. Получите твердую ссылку (учебник, веб-учебник), чтобы провести вас через процесс вычисления сложности алгоритма и, в конечном счете, "Big-O". Документируйте свои шаги и результаты, когда вы проходите процесс с помощью алгоритма вашего объекта. Выполните шаги и задокументируйте свой прогресс для нескольких сценариев, таких как наилучший случай, худший случай и средний случай. Как только вы закончите, просмотрите свою документацию и спросите себя, что потребуется, чтобы написать программу (инструмент), чтобы сделать это за вас. Это можно сделать? Сколько было бы фактически автоматизировано и сколько еще было бы ручным?
С наилучшими пожеланиями.
Это может работать для простых алгоритмов, но что же касается O (n ^ 2 lg n) или O (n lg ^ 2 n)?
Вы можете легко обмануть визуально.
И если это действительно плохой алгоритм, возможно, он не вернется даже при n = 10.
Доказательство того, что это неразрешимо:
Предположим, что у нас был некоторый алгоритм HALTS_IN_FN (Program, function), который определял, остановилась ли программа в O (f (n)) для всех n, для некоторой функции f.
Пусть P - следующая программа:
if(HALTS_IN_FN(P,f(n)))
{
while(1);
}
halt;
Поскольку функция и программа фиксированы, HALTS_IN_FN на этом входе является постоянным временем. Если HALTS_IN_FN возвращает true, программа работает вечно и, конечно же, не останавливается на O (f (n)) для любого f (n). Если HALTS_IN_FN возвращает false, программа останавливается в течение O (1).
Таким образом, у нас есть парадокс, противоречие, и поэтому программа неразрешима.
Я думаю, что это практически невозможно сделать автоматически. Помните, что O (g (n)) - верхняя граница наихудшего случая, и многие функции выполняют лучше, чем для множества наборов данных. Вам нужно будет найти список наихудших данных для каждого из них, чтобы сравнить их. Это сложная задача для многих алгоритмов.
Джеффри Л. Уитледж правильно. Простое сокращение от проблемы остановки доказывает, что это неразрешимо...
ТАКЖЕ, если бы я мог написать эту программу, я бы использовал ее для решения P vs NP и имел 1 миллион долларов... B -)
Многие люди прокомментировали, что это теоретически неразрешимая проблема. Достаточно справедливо, но кроме того, даже его решение для любых, но самых простых дел, казалось бы, невероятно сложно.
Скажем, у вас есть программа, в которой есть набор вложенных циклов, каждый из которых зависит от количества элементов в массиве. O (N ^ 2). Но что, если внутренний цикл работает только в очень специфических условиях? Скажем, в среднем он запускается в aprox log (n) случаях. Внезапно наш "очевидно" O (n ^ 2) алгоритм действительно O (n log n). Написание программы, которая могла бы определить, будет ли выполняться внутренний цикл и как часто, потенциально сложнее исходной проблемы.
Помните, что O (N) не бог; высокие константы могут и будут изменять игровое поле. Конечно, алгоритмы быстрого сортировки - это O (n log n), но когда рекурсия становится достаточно маленькой, скажем, до 20 элементов или около того, многие реализации quicksort изменят тактику на отдельный алгоритм, поскольку на самом деле быстрее сделать другой тип сортировки, говорят, что вставка сортируется с худшим O (N), но намного меньше константы.
Итак, поймите свои данные, сделайте обоснованные предположения и проверьте.
Вы также должны проявлять осторожность при выполнении таких тестов. Некоторые алгоритмы будут иметь поведение, сильно зависящее от типа ввода.
Возьмите Quicksort, например. Это худший случай O (n²), но обычно O (nlogn). Для двух входов одинакового размера.
Путешественник (я думаю, не уверен) O (n²) (EDIT: правильное значение равно 0 (n!) для аллотизма грубой силы), но большинство алгоритмов получают довольно хорошие аппроксимированные решения намного быстрее.
Это означает, что эталонная структура в большинстве случаев должна адаптироваться на разовой основе. Представьте себе что-то общее для двух упомянутых примеров. Это было бы очень сложно, возможно, непригодным для использования и, вероятно, будет давать неверные результаты.
Ну, так как вы не можете доказать, останавливается ли функция даже, я думаю, вы немного просите.
В противном случае @Godeke имеет его.
Я думаю, это невозможно в полностью автоматическом режиме, так как тип и структура ввода сильно различаются между функциями.
Я не знаю, какова ваша цель в этом, но у нас была аналогичная проблема в курсе, который я преподавал. Студенты должны были выполнять что-то, что работает с определенной сложностью.
Чтобы не выполнять свое решение вручную и читать их код, мы использовали предложенный метод @Godeke. Цель заключалась в том, чтобы найти студентов, которые использовали связанный список вместо балансированного дерева поиска, или студентов, которые внедрили сортировку пузырьков вместо сортировки кучи (т.е. реализации, которые не работают в требуемой сложности, но без фактического чтения их кода).
Удивительно, но результаты не выявили студентов, которые обманули. Это может быть потому, что наши ученики честны и хотят учиться (или просто знали, что мы это проверим;-)). Можно пропустить обмануть студентов, если входы малы, или если сам вход заказан или таков. Также можно ошибаться в отношении учеников, которые не обманывали, но имеют большие постоянные ценности.
Но, несмотря на возможные ошибки, это того стоит, так как это экономит много времени проверки.
Как говорили другие, это теоретически невозможно. Но на практике вы можете сделать обоснованное предположение о том, является ли функция O (n) или O (n ^ 2), если вы не возражаете, что иногда ошибаетесь.
Первый раз алгоритм, запускающий его на входе различных n. Настройте точки на лог-лог-график. Нарисуйте линию наилучшего соответствия через точки. Если линия хорошо соответствует всем точкам, то данные показывают, что алгоритм O (n ^ k), где k - наклон линии.
Я не статистик. Вы должны взять все это с солью. Но я действительно сделал это в контексте автоматизированного тестирования регрессий производительности. Патч здесь содержит для него некоторый код JS.
Если у вас много однородных вычислительных ресурсов, я бы потратил их на несколько выборок и сделал линейную регрессию, а затем просто взял наивысший срок.
Легко получить указание (например, "является ли линейной? сублинейной? полиномиальной? экспоненциальной" )
Трудно найти точную сложность.
Например, здесь решение Python: вы предоставляете функцию и функцию, которая создает для него параметры размера N. Вы возвращаете список значений (n, время) для построения или для выполнения регрессионного анализа. Это раз когда-то для скорости, чтобы получить действительно хороший признак, что придется много времени для минимизации помех от факторов окружающей среды (например, с помощью timeit).
import time
def measure_run_time(func, args):
start = time.time()
func(*args)
return time.time() - start
def plot_times(func, generate_args, plot_sequence):
return [
(n, measure_run_time(func, generate_args(n+1)))
for n in plot_sequence
]
И использовать его во время сортировки пузырьков:
def bubble_sort(l):
for i in xrange(len(l)-1):
for j in xrange(len(l)-1-i):
if l[i+1] < l[i]:
l[i],l[i+1] = l[i+1],l[i]
import random
def gen_args_for_sort(list_length):
result = range(list_length) # list of 0..N-1
random.shuffle(result) # randomize order
# should return a tuple of arguments
return (result,)
# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))
import pprint
pprint.pprint(times)
Это напечатано на моей машине:
[(1000, 0.078000068664550781),
(2000, 0.34400010108947754),
(3000, 0.7649998664855957),
(4000, 1.3440001010894775),
(5000, 2.1410000324249268)]