Эмпирически определить время выполнения программы?

Question

Как мы сможем угадать скорость биг-ов программы, если у нас есть значения n и соответствующее время выполнения? Имейте в виду, я не из истории CS, и я немного почитал, чтобы разобраться в контексте, но на данный момент я совершенно не в курсе.

Answer 1

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

Предположим, что среда выполнения вашей программы имеет одну из следующих «стандартных» форм:

• Полином: O (n ^k )
• Экспоненциальный: O (a ⁿ )

Еслиу него есть одна из этих форм, вот несколько полезных методов для определения констант, управляющих выражением big-O.

Полиномиальное время

Если ваша функция имеет время выполнения O (n ^k), тогда (для больших n) время выполнения будет приблизительно иметь вид T (n) = c · n ^k .Действительно полезный способ выяснить, что такое c и k, - это использовать log-log plot .Предположим, что вы посмотрите на значения log T (n) и log (c · n ^k ).Обратите внимание, что

log (c · n ^k ) = log c + k log n

Это означает, что если у вас есть log-logplot, где зависимая переменная - log T (n), а независимая переменная - log n, тогда любой многочлен будет выглядеть как линия.Затем вы можете использовать любой стандартный метод линейной регрессии, чтобы получить наиболее подходящую линию, соответствующую линии, из которой вы можете восстановить log c и k в приведенном выше выражении.Оттуда время выполнения вашего алгоритма будет O (n ^k )

Экспоненциальное время

Если ваше время выполнения экспоненциально (то есть O (a ⁾ⁿ ) для некоторых а), тогда вы можете использовать стандартный лог-план для восстановления базы а.Если ваша функция приблизительно равна T (n) = c · a ⁿ для некоторых констант a и c, то взятие логарифма с правой стороны дает вам

log (c · a ⁿ ) = log c + n log a

Это означает, что если вы построите T (n) вместо log c + n log a, вы вернетеськакая-то прямая линия.Затем вы можете выполнить регрессию для восстановления журнала c и журнала a, из которого время выполнения может быть считано как O (a ⁿ ).

Надеюсь, это поможет!

Answer 2

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

Answer 3

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

Для эмпирического результата я бы начал с n = 1 до n = 10, затем продолжал бы увеличивать n на 10% каждый раз, рисуя график, пока это не займет слишком много времени.Алгоритмы, использующие память, пропорциональную n, часто имеют «скачок» во времени выполнения, когда ваши требования к памяти переходят на следующий уровень кеша;увеличение n на 10% означает, что вы можете найти эти прыжки.

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