En la teoría de la complejidad computacional , un recurso computacional es un recurso utilizado por algunos modelos computacionales en la solución de problemas computacionales .
Los recursos computacionales más simples son el tiempo de cálculo , la cantidad de pasos necesarios para resolver un problema, y el espacio de memoria , la cantidad de almacenamiento necesaria mientras se resuelve el problema, pero se han definido muchos recursos más complicados. [ cita requerida ]
Un problema computacional generalmente se define en términos de su acción sobre cualquier entrada válida. Algunos ejemplos de problemas pueden ser "dado un entero n , determinar si n es primo", o "dados dos números x e y , calcular el producto x * y ". A medida que las entradas se hacen más grandes, la cantidad de recursos computacionales necesarios para resolver un problema aumentará. Por lo tanto, los recursos necesarios para resolver un problema se describen en términos de análisis asintótico , identificando los recursos como una función de la longitud o el tamaño de la entrada. El uso de recursos a menudo se cuantifica parcialmente utilizando la notación Big O.
Los recursos computacionales son útiles porque podemos estudiar qué problemas se pueden calcular con una cierta cantidad de cada recurso computacional. De esta manera, podemos determinar si los algoritmos para resolver el problema son óptimos y podemos hacer afirmaciones sobre la eficiencia de un algoritmo . El conjunto de todos los problemas computacionales que se pueden resolver utilizando una cierta cantidad de un determinado recurso computacional es una clase de complejidad , y las relaciones entre diferentes clases de complejidad son uno de los temas más importantes en la teoría de la complejidad.
El término "recurso computacional" se utiliza comúnmente para describir equipos y software informáticos accesibles. Véase Computación de utilidad .
Se han hecho algunos esfuerzos para cuantificar formalmente la capacidad de computación. Se ha utilizado una máquina de Turing limitada para modelar cálculos específicos utilizando el número de transiciones de estado y el tamaño del alfabeto para cuantificar el esfuerzo computacional necesario para resolver un problema particular. [1] [2]