Как можно проверить сложность времени «экспериментально»?

Question

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

Answer 1

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

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

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

for n = 5 to 10000 //n: problem size
  long start = System.time()
  executeAlgorithm(n)
  long end = System.time()
  long totalTime = end - start

  double ratio = (double) time / (n * n)
end

. Когда n движется к бесконечности, это соотношение ...

• сходится к нулю? Тогда ваше предположение слишком низкое . Повторите с чем-то большим (например, n ^ 3)
• расходится до бесконечности? Тогда ваше предположение слишком высоко . Повторите с чем-то меньшим (например, nlogn)
• сходится к положительной постоянной? Бинго! Ваше предположение на деньги (по крайней мере, приближается к теоретической сложности для столь больших n значений, как вы пытались)

В основном используется определение большой O-нотации, что f(x) = O(g(x)) <=> f(x) < c * g(x) - f(x) - это фактическая стоимость вашего алгоритма, g(x) - это предполагаемое вами предположение, а c - константа. Таким образом, вы пытаетесь экспериментально найти предел f(x)/g(x); если ваша догадка достигнет реальной сложности, это соотношение будет оценивать константу c.

Answer 2

Сложность алгоритма определяется как (что-то вроде :)

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

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

Это даст вам хорошую "теоретическую" оценку.
Если вы хотите получить реальные цифры с другой стороны - используйте profiling .

Answer 3

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

1. сброс конвейера процессора
2. Кеш пропускает
3. Сборка мусора
4. Другие процессы на машине

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

Answer 4

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

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

Answer 5

Могу ли я предложить использовать профилировщик ANTS. Он предоставит вам такие подробности, когда вы запустите ваше приложение с «экспериментальными» данными.

Answer 6

да.

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