Это хорошая идея иметь важную информацию во время разработки, такой как нотация Ландау, чтобы знать временные затраты функций. Значит, это должно быть задокументировано в источниках, не так ли?
Я ищу инструменты, которые могут вычислить это.
Поддержка инструментов нотации Ландау (ide)
comment
Интересно... Я не знаю никаких инструментов, которые могут вычислить Big-O фрагмента кода. Не уверен, что такие вещи существуют (или даже возможны), но если они есть, мне было бы интересно их увидеть.
- person FrustratedWithFormsDesigner schedule 26.04.2010
comment
Например, если разработчики языка будут документировать большие 0 для атомарных операций, это может быть возможно. Или, если у вас есть метод с некоторыми параметрами (коллекциями), можно запустить модульный тест и зарегистрировать продолжительность выполнения метода с разной длиной коллекции. Вот как можно рассчитать O.
- person Jeriho schedule 27.04.2010
Ответы (1)
В общем случае асимптотическая сложность произвольного алгоритма неразрешима по теореме Райса.
Но на практике вы часто можете сделать хорошее предположение, многократно запуская алгоритм на различных входных данных (с размерами, охватывающими несколько порядков), записывая фактическое время процессора и подгоняя кривую. (Вы должны отбрасывать точки данных с очень коротким временем выполнения, так как в них будет преобладать шум. Кроме того, в средах выполнения JIT, таких как виртуальная машина Java, обязательно запустите функцию на некоторое время перед запуском времени, чтобы убедиться, что виртуальная машина согрелся.)
person
Mechanical snail
schedule
22.06.2011
