[Algorithm] 시간 복잡도와 공간 복잡도

'알고리즘을 효율적을 짠다 = 시간과 공간을 최소화한다' 알고리즘의 효율성을 판단할 때, 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)를 따진다. 백준, 프로그래머스에서도 알고리즘을 평가할 때 시간과 메모리 제한을 두는 것도 다 이런 이유에서다. 시간 복잡도(Time complexity) 개념와 예시 '입력값의 증가에 대한 연산 횟수 증가분' 시간 복잡도는 그저 실행 시간을 측정하는 것이 아니다. 실행 시간은 측정을 위한 프로그램이 필요할뿐더러 수행 환경에 따라 실행 시간이 달라질 수 있다. 이에 따라 입력값이 증가함에 따라 연산 횟수가 어떤 비율로 증가하는가에 초점을 두고 시간 복잡도를 측정한다. 시간 복잡도는 Worst Case, 즉 가장 최악으로 시간이 걸..

2022.04.16