연산 자원

연산 자원, 계산 자원 또는 연산 리소스(Computational resource)는 계산 복잡도 이론에서 연산 문제를 해결하기 위해 일부 연산 모델에서 사용되는 자원이다.

가장 간단한 연산 자원은 문제를 해결하는 데 필요한 단계 수인 연산 시간과 문제를 해결하는 데 필요한 저장 공간인 메모리 공간이지만 훨씬 더 복잡한 자원이 정의되었다.

연산 문제는 일반적으로 유효한 입력에 대한 동작으로 정의된다. 문제의 예로는 "정수 n이 주어지면 n이 소수인지 판단합니다" 또는 "두 숫자 x와 y가 주어지면 x*y 곱을 계산합니다" 등이 있다. 입력이 커질수록 문제를 해결하는 데 필요한 연산 자원의 양도 늘어난다. 따라서 문제를 해결하는 데 필요한 자원은 자원을 입력 길이 또는 크기의 함수로 식별함으로써 점근적 분석 측면에서 설명된다. 리소스 사용량은 Big O 표기법을 사용하여 부분적으로 수량화되는 경우가 많다.

연산 자원은 각 연산 자원의 일정량으로 어떤 문제를 연산할 수 있는지 연구할 수 있기 때문에 유용하다. 이러한 방식으로 문제 해결을 위한 알고리즘이 최적인지 여부를 판단하고 알고리즘의 효율성에 대해 설명할 수 있다. 일정량의 특정 연산 자원을 사용하여 해결할 수 있는 모든 연산 문제의 집합이 복잡도 종류이며, 서로 다른 복잡도 종류 간의 관계는 복잡도 이론에서 가장 중요한 주제 중 하나이다.