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