Программно получить эффективность кода Big-O

Легко получить признак (например, "действительно ли функция линейна? подлинейный? многочлен? экспоненциал")

трудно найти точную сложность.

, Например, вот решение 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)]

Необходимо также заботиться при выполнении таких сравнительных тестов. Некоторые алгоритмы будут иметь поведение в большой степени зависящим от входного типа.

Берут Quicksort, например. Это - худший случай O (nВІ), но обычно O (nlogn). Для двух исходных данных того же размера.

коммивояжер (я думаю, не уверенный) O (nВІ) ( РЕДАКТИРОВАНИЕ: правильное значение 0 (n!) для грубой силы algotithm ), но большинство алгоритмов получает довольно хорошие приближенные решения намного быстрее.

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

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

Иначе @Godeke имеет его.

Jeffrey L Whitledge корректен. Простое сокращение от проблемы остановки доказывает, что это неразрешимо...

КРОМЕ ТОГО, если бы я мог бы записать эту программу, я использовал бы ее, чтобы решить P по сравнению с NP и иметь $1 миллион... B-)

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

Говорят, что у Вас есть программа, которая имеет ряд вложенных циклов, каждого на основе количества объектов в массиве. O (n^2). Но что, если внутренний цикл только выполняется в очень определенном стечении обстоятельств? Скажите, в среднем, это выполняется в приблизительном журнале (n) случаи. Внезапно наш, "очевидно", O (n^2) алгоритм действительно O (n, регистрируют n). Запись программы, которая могла определить, будет ли внутренний цикл выполнен, и как часто, является потенциально более трудной, чем исходная проблема.

Помнят, что O (N) не является богом; высокие константы могут и изменять игровую площадку. Алгоритмы Quicksort являются O (n, регистрируют n), конечно, но когда рекурсия становится достаточно небольшой, скажите вниз приблизительно 20 объектам, много реализаций quicksort изменят тактику на отдельный алгоритм, поскольку это на самом деле более быстро, чтобы сделать другой тип вида, сказать вид вставки с худшим O (N), но намного меньшая константа.

Так, поймите свои данные, выскажите образованные предположения и тест.

Я предполагаю, что это не возможно полностью автоматическим способом начиная с типа, и структура входа отличается много между функциями.

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

Это могло работать на простые алгоритмы, но что относительно O (n^2 LG n) или O (n lg^2 n)?

Вас можно было дурачить визуально очень легко.

И если бы это - действительно плохой алгоритм, возможно, это не возвратилось бы даже на n=10.

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

Я удивлен видеть столько попыток утверждать, что можно "измерить" сложность секундомером. Несколько человек дали правильный ответ, но я думаю, что существует все еще комната, чтобы убедительно доказать существенную точку зрения.

1. сложность Алгоритма не является вопросом "о программировании"; это - вопрос "об информатике". Ответ на вопрос требует анализа кода с точки зрения математика, такого, что вычисления Большой-O сложности являются практически формой математического доказательства. Это требует очень глубокого понимания фундаментальных компьютерных операций, алгебры, возможно, исчисление (пределы) и логика. Никаким объемом "тестирования" нельзя заменить тот процесс.

2. Проблема остановки применяется, таким образом, сложность алгоритма существенно неразрешима машиной.

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

4. Для любого серьезно рассматривающего запись такого инструмента, я предлагаю следующее осуществление. Выберите довольно простой алгоритм, такой как Ваш любимый вид, как Ваш подчиненный алгоритм. Заставьте твердую ссылку (книга, веб-учебное руководство) приводить Вас посредством процесса вычисления сложности алгоритма и в конечном счете "Большого-O". Зарегистрируйте свои шаги и результаты, поскольку Вы проходите процесс со своим подчиненным алгоритмом. Выполните шаги и зарегистрируйте свой успех для нескольких сценариев, таких как лучший случай, худший случай и средний случай. После того как Вы сделаны, рассматриваете свою документацию и спрашиваете себя, что она взяла бы для записи программы (инструмент), чтобы сделать это для Вас. Это может быть сделано? Сколько было бы на самом деле автоматизировано, и сколько все еще будет ручным?

С наилучшими пожеланиями.

Мне любопытно относительно того, отчего получается, что Вы хотите смочь сделать это. По моему опыту, когда кто-то говорит: "Я хочу установить сложность во время выполнения этого алгоритма", они не спрашивают, что они думают, что спрашивают. То, что Вы, скорее всего, спрашиваете, - то, что является реалистической производительностью такого алгоритма для вероятных данных. Вычисление Большой-O из функции имеет разумную утилиту, но существует столько аспектов, которые могут изменить "реальную производительность во время выполнения" алгоритма в реальном использовании, что ничто не бьет инструментарий и тестирование.

, Например, следующие алгоритмы имеют то же, точное Большой-O (дурацкий псевдокод):

пример 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..., но один из них, использует строку ordinality и одного из них столбец использования ordinality. Оказывается, что из-за местности ссылочной и когерентности кэш-памяти Вы могли бы иметь два полностью различное фактическое время выполнения, особенно в зависимости от фактического размера нечто массива. Это даже не начинает касаться фактических рабочих характеристик того, как алгоритм ведет себя, если это - часть части программного обеспечения, которое имеет некоторый встроенный параллелизм.

, чтобы Не быть отрицательным nelly, но большой-O инструмент с узким объемом. Это очень полезно, если Вы - глубоко внутренний алгоритмический анализ или если Вы пробуете к , доказывают что-то об алгоритме, но если Вы делаете коммерческую разработку программного обеспечения, доказательство находится в пудинге, и Вы собираетесь хотеть иметь фактические показатели производительности для принятия интеллектуальных решений.

За Ваше здоровье!

Короткий ответ - то, что это невозможно, потому что константы имеют значение .

, Например, я мог бы записать функцию, которая работает в O((n^3/k) + n^2). Это упрощает до O (n^3), потому что как n бесконечность подходов, эти n^3 термин будет доминировать над функцией, независимо от константы k.

Однако, если k является очень большим в вышеупомянутой функции в качестве примера, функция, будет казаться, будет работать в почти точно n^2 до некоторой точки перехода, в которой эти n^3 семестр начнет доминировать. Поскольку константа k будет неизвестна любому профильному инструменту, будет невозможно знать как большой набор данных тестировать целевую функцию с. Если k может быть произвольно большим, Вы не можете обработать данные тестирования для определения большого о времени выполнения.

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

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

До инспекция кода методы, ни один не существует. Но оснащение Вашего кода для выполнения в различных длинах и вывод простого файла (RunSize RunLength был бы достаточно) должны быть легкими. Генерация надлежащих данных тестирования могла быть более сложной (некоторая работа алгоритмов, лучшая/хуже с частично заказанными данными, таким образом, Вы захотите генерировать данные, которые представили Ваш нормальный пример использования ).

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

Доказательство того, что это неразрешимо:

Предположим, что у нас был некоторый алгоритм HALTS_IN_FN (Программа, функция), который определял, программа остановлена ​​в 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) раз.

Таким образом, мы имеем парадокс, противоречие, и поэтому программа неразрешима.

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

Чтобы не перебирать решение вручную и не читать их код, мы использовали метод, предложенный @Godeke. Задача состояла в том, чтобы найти студентов, которые использовали связанный список вместо сбалансированного дерева поиска, или студентов, которые реализовали пузырьковую сортировку вместо сортировки по куче (т.е. реализации, которые не работают с требуемой сложностью, но фактически не читают свой код).

Удивительно, но результаты не выявили студентов, которые обманывали. Это может быть потому, что наши студенты честны и хотят учиться (или просто знали, что мы это проверим ;-)). Можно пропустить читающих учеников, если входы небольшие, или если сам ввод заказан или что-то в этом роде. Также можно ошибаться в отношении учеников, которые не обманывали, но имели большие постоянные значения.

Но, несмотря на возможные ошибки, оно того стоит, поскольку экономит много времени на проверку.

Как говорили другие, это теоретически невозможно. Но на практике вы можете предположить, является ли функция O ( n ) или O ( n ^ 2), если вы не против иногда ошибаться.

Первый раз алгоритм, запускающий его на входе различных n . Нанесите точки на логарифмический график . Проведите через точки наиболее подходящую линию. Если линия хорошо соответствует всем точкам, то данные предполагают, что алгоритм - O ( n ^ k ), где k - наклон линии

Я не статистик. Вы должны относиться ко всему этому с недоверием. Но на самом деле я сделал это в контексте автоматизированного тестирования на снижение производительности.