В теории сложности вычислений вычислительный ресурс — это ресурс, используемый некоторыми вычислительными моделями при решении вычислительных задач .
Простейшими вычислительными ресурсами являются время вычислений (количество шагов, необходимых для решения задачи) и объем памяти (объем памяти, необходимый для решения задачи), но были определены и многие более сложные ресурсы. [ нужна цитата ]
Вычислительная задача обычно определяется с точки зрения ее действия на любой допустимый входной сигнал . Примерами задач могут быть «данное целое число n , определить, является ли n простым» или «данные два числа x и y , вычислить произведение x * y ». По мере увеличения входных данных количество вычислительных ресурсов, необходимых для решения проблемы, будет увеличиваться. Таким образом, ресурсы, необходимые для решения проблемы, описываются с точки зрения асимптотического анализа путем определения ресурсов как функции длины или размера входных данных. Использование ресурсов часто частично оценивается с помощью нотации Big O.
Вычислительные ресурсы полезны, потому что мы можем изучить, какие задачи можно решить с использованием определенного количества каждого вычислительного ресурса. Таким образом, мы можем определить, являются ли алгоритмы решения задачи оптимальными, и сделать выводы об эффективности алгоритма . Набор всех вычислительных задач, которые можно решить с использованием определенного количества определенного вычислительного ресурса, представляет собой класс сложности , а отношения между различными классами сложности являются одной из наиболее важных тем теории сложности.
Термин «вычислительный ресурс» обычно используется для описания доступного компьютерного оборудования и программного обеспечения. См. «Коммунальные вычисления» .
Были предприняты некоторые усилия по формальной количественной оценке вычислительных возможностей. Ограниченная машина Тьюринга использовалась для моделирования конкретных вычислений с использованием количества переходов состояний и размера алфавита для количественной оценки вычислительных усилий, необходимых для решения конкретной проблемы. [1] [2]