알고리즘 분석

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

알고리즘 분석(영어: analysis of algorithms)은 컴퓨터 과학에서 알고리즘을 실행하는데 필요한 (시간과 기억 용량과 같은) 자원의 수를 결정하는 일을 가리킨다. 대부분의 알고리즘은 임의의 길이의 입력과 함께 동작하도록 구성된다. 일반적으로 알고리즘의 효율성과 실행 시간은 단계의 수 (시간 복잡도)와 기억 위치 (공간 복잡도)에 대한 입력 길이와 관련한 함수로 나타낼 수 있다.

알고리즘 분석이 더 광범위한 계산 복잡도 이론의 중요한 부분인데, 주어진 계산 문제를 해결하는 알고리즘에 필요한 자원에 대한 이론적 견적을 제공한다. 이러한 견적들은 효율적인 알고리즘을 검색하는데 도움을 준다.

알고리즘 분석에서는 보통 점근적(asymptotic) 의미로 복잡도를 계산한다. 즉, O표기법, Ω표기법, Θ표기법과 같은 방법으로 일정 크기의 입력 자료에 대한 복잡도 함수를 구한다. 예를 들어, 이진 탐색의 단계 수는 입력 자료의 크기에 대수적으로 비례하는데, 이것을 O(\log n) 또는 대수 시간이라 한다. 점근적인 방법을 사용하는 이유는, 같은 알고리즘이라도 입력 자료의 크기에 따라 수행 시간에 차이가 나는 것을 보완하기 위해서이다. 이런 수행 시간의 차이는 상수 배로 나타나는데, 이때의 상수를 숨은 상수(hidden constant)라고 한다.

시간 효율성의 추산은 수행 단계로서 정의하는 것에 의존한다. 의미있는 분석을 하려면, 각 단계에서 걸리는 수행 시간에 상한이 있어야 한다. 예를 들어, 두 수의 덧셈을 하나의 단계라 할 때, 각 수가 지극히 크면, 덧셈이 일정한 시간 내에 완료된다고 할 수 없기 때문이다. (2자리수의 덧셈을 하는 경우와 1000자리수의 덧셈을 하는 경우를 비교하여 생각해보라.)

비용 모델[편집]

두 개의 비용 모델이 일반적으로 쓰인다:[1][2][3][4][5]

  • 동일 비용 모델(uniform cost model) / 동일 비용 측정(uniform-cost measurement): 수반되는 수의 크기에 관계 없이 일정한 비용을 모든 기계 작동에 할당한다.
  • 대수 비용 모델(logarithmic cost model) / 대수 비용 측정(logarithmic-cost measurement): 수반되는 비트의 수와 비례하여 비용을 모든 기계 작동에 할당한다.

대수 비용 모델은 사용하기 더 번거롭기 때문에 암호학 분야 등의 임의 밀도 연산 알고리즘 분석과 같이 필요할 때에만 이용한다.

실행 시간 분석[편집]

실행 시간 분석은 입력 크기가 증가함에 따라 알고리즘실행 시간이 늘어나는 것을 측정하고 예측하는 이론적 분류이다. 실행 시간의 효율성은 컴퓨터 과학의 주된 관심사이다. 프로그램 하나는 실행을 마치는데 수 초, 수 시간, 수 년이 걸릴 수 있으며 이는 알고리즘의 수행 방식에 따라 결정된다. (성능 분석도 참고)

같이 보기[편집]

참조[편집]

  1. (1974) 《The design and analysis of computer algorithms》. Addison-Wesley Pub. Co., section 1.3
  2. Juraj Hromkovič (2004). 《Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography》. Springer, 177–178쪽. ISBN 978-3-540-14015-3
  3. Giorgio Ausiello (1999). 《Complexity and approximation: combinatorial optimization problems and their approximability properties》. Springer, 3–8쪽. ISBN 978-3-540-65431-5
  4. (2005) 《Complexity theory: exploring the limits of efficient algorithms》. Berlin, New York: Springer-Verlag, 20쪽. ISBN 978-3-540-21045-0
  5. Robert Endre Tarjan (1983). 《Data structures and network algorithms》. SIAM, 3–7쪽. ISBN 978-0-89871-187-5