Как оценить время и потребление памяти программы, использующей рекурсию Java

Question

Я решаю проблему Knight's tour. Размер стола составляет 5X5, а отправной точкой для тура может быть любой квадрат. Я нашел все возможные открытые решения и вычислил использование памяти, а также время использования программы. Я использую рекурсию и на каждом рыцарском ходу. Я вычисляю следующие возможные шаги для рыцаря.

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

Answer 1

Для этого в General не существует инструментов Java или инструментов на других языках программирования. Он связан с Turing halting problem, который, как известно, является неразрешимым.

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

E.g. если вы знаете, что во время выполнения О (2^п), что означает

T = C * (2^N) (+ пренебрежимо части)

можно вычислить константу с установкой в ​​уравнении конкретное время, например n = 5, например. если измерить Т = 10с при п = 5:

10s = с * (2^5)

==> с = 10 с/(2^5)

Это только пример (Я не знаю, является ли ваша проблема O (2^n)).

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

Answer 2

Что такое масштабирование вашего гораздо большего размера стола?

Обратите внимание, что может быть значительной разницей между расчетным потреблением (как времени, так и памяти) и потреблением, оцененным по сложности. Предыдущий ответ (Thomas Philipp) правильно за исключением одной детали:

т = с * (2^п) (+ пренебрежимо части)

С одной теоретической точки зрения, это противоречие: если вы беспокоитесь о факторе c, вы также можете заботиться о так называемых «пренебрежимых частях». Те, кто выпадает из определения сложности, - это мир, где единственный член, который считается, является пределом, равным + бесконечности, - O (2^N).

В практическом плане проверьте сложность настройки и любые надвигающиеся вторичные термины в вашем алгоритме. Например, одна программа, над которой я работал, имела прямое решение O (n^2 log n). Был O (n log n) предварительная работа и некоторые O (n) служебные данные.

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

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