![Featured Image for [알고리즘] 알고리즘 분석](https://ih1.redbubble.net/image.1502642451.8092/st,small,507x507-pad,600x600,f8f8f8.jpg)
어떤 알고리즘이 있을 때, 우리는 이 알고리즘을 어떻게 분석하는게 좋을까? 바로 구현 / 정확성 / 효율성 세 가지 핵심 요소를 통해 대상 알고리즘을 효과적으로 분석할 수 있다.
구현은 알고리즘이 어떻게 구조화되고 작성되었는지를 의미하며, 코드 레벨에서의 설계와 구현 방식에 대한 부분이다.
정확성은 알고리즘이 기대한 대로 정확하게 동작하는지 평가하는 요소로, 원하는 결과를 항상 도출해낼 수 있는지 증명하는 것이다.
효율성은 알고리즘이 얼마나 빠르게 동작하는지를 나타내며, 이는 시간과 자원의 소비를 분석하는 중요한 지표이다.
복잡도는 알고리즘이 자원을 얼마나 효율적으로 사용하는지를 나타내는 개념이다. 자원에는 주로 시간과 공간(메모리)이 포함되며, 복잡도는 이 자원들이 입력 크기(n)에 따라 어떻게 변하는지를 수학적으로 표현한다!
시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간이 입력 크기 n에 따라 어떻게 변하는지를 나타낸다. 입력 크기가 커질수록 알고리즘이 얼마나 더 많은 시간을 소모하는지를 분석한다.
공간 복잡도는 알고리즘이 사용하는 메모리의 양이 입력 크기 n에 따라 어떻게 변하는지를 나타낸다. 입력 크기가 커질수록 알고리즘이 얼마나 많은 메모리를 차지하는지를 분석한다.
시간 복잡도와 공간 복잡도는 모두 중요한 요소지만, 현대 컴퓨터 기술의 발전으로 공간 복잡도는 메모리 용량의 증가로 인해 비교적 아주 살짝 덜 신경 쓸 수 있게 되었다. 내가 중점적으로 볼 것은 바로 시간 복잡도이다. 이는 여전히 알고리즘 효율성의 핵심 관심사이며, 시간 복잡도를 평가할 떄는 세 가지 주요 경우를 고려해야 한다:
대부분의 경우, 최악의 상황에서의 성능이 가장 중요한 평가 기준이 된다. 이는 알고리즘이 가장 불리한 상황에서도 얼마나 성능을 유지할 수 있는지가 시스템의 안정성과 신뢰성에 중요한 영향을 미치기 때문이다.
알고리즘을 분석하고 접근하는 방법에는 크게 점근적 접근 방법과 재귀적 접근 방법이 존재한다. 하나 하나 볼륨이 크기 때문에, 링크를 나누어 정리해놓았다.