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 para resolver el problema, pero se han definido muchos recursos más complicados. [ cita necesaria ]
Un problema computacional generalmente se define [ cita necesaria ] en términos de su acción sobre cualquier entrada válida. Ejemplos de problemas podrían ser "dado un número 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 aumentan, aumentará la cantidad de recursos computacionales necesarios para resolver un problema. Así, los recursos necesarios para resolver un problema se describen en términos de análisis asintótico , identificando los recursos en función de la longitud o tamaño de la entrada. El uso de recursos a menudo se cuantifica parcialmente utilizando la notación O grande .
Los recursos computacionales son útiles porque podemos estudiar qué problemas se pueden calcular en una determinada 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 usando 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. Consulte Computación de utilidades .
Ha habido algunos esfuerzos para cuantificar formalmente la capacidad informática. 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 requerido para resolver un problema particular. [1] [2]