Можно ли оценить объем оперативной памяти, необходимой для сложности пространства Тьюринга?

Question

Машины Тьюринга могут учитывать сложность как в пространстве (пространство памяти на лентах), так и во времени.

Существуют классы, такие как PSPACE и EXPSPACE.

Далее, мы можем представить алгоритмы, которые определеннов PSPACE.

http://www.springerlink.com/content/3hqtq11mqjbqfj2g/

Однако, когда я на самом деле кодирую программы, некоторые программы работают быстрее, чем другие, некоторые программы занимают меньше памяти (RAM), чем другие.

Предположительно, если я кодирую алгоритм PSPACE для решения проблемы X, а также алгоритм EXPSPACE для решения той же проблемы, программа EXPSPACE должна использовать гораздо больше ОЗУ, чем код PSPACE.

Есть ли способ оценить, каксколько оперативной памяти будет задействовано, исходя из теоретической оценки алгоритма запуска?

Answer 1

Предположительно, если я кодирую алгоритм PSPACE для решения проблемы X, а также алгоритм EXPSPACE для решения той же проблемы, программа EXPSPACE должна использовать гораздо больше ОЗУ, чем код PSPACE.

Вы предполагаете, что ошиблись.

Эти классы сложности описывают асимптотический рост памяти, необходимый для выполнения алгоритма. Они абсолютно ничего не говорят о фактическом объеме требуемой оперативной памяти.

В принципе, для некоторого размера проблемы n , выше этого размера EXPSPACE будет использовать больше памяти, чем PSPACE, но для всего, что ниже n , вы не можете ничего сказать как алгоритмы O (n ² ) могут работать быстрее, чем алгоритмы O (n) для небольших n ).

Answer 2

В принципе нет.На практике иногда.

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

Если вы знаете, что алгоритм находится в PSPACE, вы можете предположить, что используемое им пространство не просто ограничен полиномом, он описан полиномом.Возможно, это не так, но для многих алгоритмов это правда.Затем вы можете вычислить (или измерить) пространство, используемое для различных входных размеров, и попытаться сопоставить полином с данными.

В общем, это довольно бесполезно (потому что без знания порядка полинома естьбесконечно много возможных подгонок).Но на практике, если вы знаете, что используемое пространство, скажем, O (n), и у вас есть представление о том, какие виды ввода приведут к использованию пространства в худшем случае, вы можете сделать довольно точные прогнозы.Если для обработки 1 МБ ввода требуется 10 МБ ОЗУ, а для обработки 2 МБ - 20 МБ, то для обработки 10 МБ часто требуется около 100 МБ ОЗУ.Но вы получите эту информацию только из более детального знания алгоритма, чем просто из-за сложности его полиномиального пространства.