3.2 계산문제 분석

계산문제 분석은 세 가지 질문에 대한 답변에 따라 달라진다.

1. 계산문제 computational problem 란 무엇인가? 계산문제 분석에 대한 일반적인 이론을 개발하기 위해 우리는 결정문제 decision problem 라는 특수한 클래스의 문제를 분리하고 분석에 집중할 것, 이런 식으로 우리 자신을 제한하면 풍부한 구조의 이론을 개발할 수 있다. 이렇게 개발된 이론은 결정 문제 이외에도 폭넓게 응용될 수 있다.
2. 주어진 계산문제를 해결하기 위해 알고리즘을 어떻게 설계할 수 있을까?
3. 주어진 계산문제를 해결하는 데 필요한 최소 자원은 무엇인가?

 

컴퓨터는 다양한 종류의 자원을 사용하지만 시간, 공간, 에너지에 대해 대부분의 주의를 기울일 것, 

 

에너지 요구사항에 대한 연구로 인해 가역적 고전계산 reversible classical computation 라는 주제에 관심이 높아짐, 

 

3.2.1 계산 자원을 정량화하는 방법

계산 모델이 다르면 계산에 필요한 자원도 달라진다. 

계산모델의 비교적 사소한 변경에도 흔들리지 않는 자원 요구사항 정량화 방법이 필요, 이를 위해 개발된 도구 중 하나는 점근적 표기법 asymptotic notation 이며 함수의 본질적 거동 essential behavior 을 요약하는 데 사용할 수 있다.