시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)

알고리즘 분석 동일한 작업을 수행하는 알고리즘이라 할지라도, 다른 성능을 갖게 될 수 있습니다. 따라서 알고리즘마다 평가를 하기 위한 기준이 필요한데, 그 기준으로 시간 복잡도(time complexity)와 공간 복잡도(space complexity)를 사용합니다. 이 복잡도가 낮을수록 좋은 알고리즘이라고 평가할 수 있습니다. 시간 복잡도(Time Complexity) 시간 복잡도는 알고리즘의 수행 시간을 평가하며, 점근적 표기법 중에서도 big O 표기법을 이용해 시간 복잡도를 표기합니다. 이 점근적 표기법은 연산의 횟수를 계산할 때, 불필요한 상수 계수 및 상수 항을 제거해서 표현하는 방법을 의미합니다. 알고리즘의 수행 시간은 실행 환경에 따라서 천차만별이기 때문에, 기본 연산(primitive operations)의 실행 횟수를 기준으로 평가하며, 기본 연산은 다음과 같습니다. 데이터 입출력 산술 연산 제어 연산 위의 3가지 연산을 수행한 횟수를 센 것을 기준으로 수행 시간을...

원문링크 : 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)