Инструмент Algorithm Analysis для [закрытого] Java
1 ответ
Это не то, что обычно выполняется автоматически. Анализ Big-O - нетривиальная вещь.
Вы уверены, что вместо этого ищете профилировщик?
Большой анализ алгоритмов обычно выполняется на этапе проектирования, карандашом и бумагой. Возможно, что некоторые люди пишут простые программы и используют автоматизированные инструменты для измерения и сравнения прототипов реализации различных алгоритмов, чтобы помочь в анализе, но даже в этом весьма гипотетическом случае Java НЕ будет предпочтительным языком (возможно, Haskell).
Для приложений, написанных на практичном (но теоретически уродливом!) Языке, таком как Java, обычно вы разрабатываете и анализируете алгоритм до реализации, а затем, как только вы переводите его на Java, вы профилируете и оптимизируете как / если необходимо . На этом этапе вы должны уже знать сложность Big-O вашего алгоритма.
Это может быть для вас сюрпризом, но предположим, что у вас есть реализация какого-то алгоритма, а затем вы оптимизируете его так, чтобы он стал в два раза быстрее. Может, раза три. Может, в десять раз быстрее.Может быть, в миллион раз быстрее !!!
И все же, с точки зрения анализа Big-O, его сложность остается прежней! Если бы у вас был линейный алгоритм, улучшенная оптимизированная версия, работающая в миллион раз быстрее, оставалась бы линейной! Если бы он был квадратичным, так и остался бы!
Это связано с тем, что постоянный коэффициент не имеет значения для асимптотического анализа (т.е. насколько быстро он растет, когда размер входных данных приближается к бесконечности?). Миллион - это большое число, но это все равно константа.
Еще одним усложняющим фактором является то, что асимптотический анализ фактически имеет порог , после которого границы сохраняются. То есть для меньших входных данных эти границы могут быть нарушены, но начиная с этого порога до бесконечности, границы должны соблюдаться. Это очень затрудняет автоматический анализ путем измерения, поскольку вы не знаете, достигли ли вы порога или нет.
Я рекомендую прочитать некоторые учебники по начальным компьютерным наукам, чтобы больше узнать об этом предмете.
Забавный факт: невозможно сказать, остановится ли когда-нибудь программа. Это известно как проблема остановки . Поначалу это может показаться смешным, но это имеет множество серьезных теоретических последствий.
См. Также
- Как вычислить порядок (большой O) для более сложных алгоритмов (например, быстрая сортировка)
- Big O, как вы его вычисляете / аппроксимируете?
- Программное обеспечение эффективности кода Big-O