알고리즘의 성능을 판단하는 두 가지 기준을 말한다.
시간 복잡도 (Time Complexity)
알고리즘을 수행하는데 이루어진 연산의 횟수이며 여기에서 연산의 종류는 산술, 대입, 비교, 이동을 말한다.
연산의 횟수는 변수의 갯수에 의존하여 결정된다. 때문에 아래 빅오 표기법과 같이 변수의 갯수에 따른 증가 추세를 나타내 보다 간편하게 표현한다.
- 빅오 표기법 (big-oh notation)Permalink
시간 복잡도 함수에서 불필요한 연산을 제거하여 보다 간편하게 시간/공간 복잡도를 표기하는 방법이다.
빅오 표기법은 정확한 연산의 갯수가 아니라 알고리즘의 일반적인 증가 추세를 표현한다. 알고리즘이 n에 정비례하여 실행 시간을 가질 경우 시간 복잡도가 O(n)이라 표시하고 ‘big-oh of n’이라고 읽는다.
동일한 알고리즘이라도 입력되는 데이터에 따라 다른 실행시간을 보일 수 있다. 예를 들어 정렬 알고리즘의 경우 대부분 정렬되어있는 데이터와 그렇지 않은 데이터의 시간 복잡도가 크게 차이날 수 있다. 이 때 데이터의 집합에 따라 세가지 경우에 따라 나누어 평가한다.
- 최선의 경우(Best Case) : 실행 시간이 가장 적은 경우를 말한다.
- 평균적인 경우(Average Case) : 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균 수행 시간을 말한다.
- 최악의 경우(Worst case) : 알고리즘의 수행 시간이 가장 오래 걸리는 경우를 말한다.
시간 복잡도를 계산할 때에는 최악의 경우를 주로 사용한다.
공간 복잡도 (Space Complexity)
프로그램의 실행~완료까지 필요로하는 자원 공간의 양을 말한다.
총 공간은 고정 요구 공간과 가변 요구 공간*의 합으로 나타낼 수 있다.
*가변 요구 공간 : 해결하려는 문제의 인스턴스에 의존하는 크기를 가진 공간. 즉, 동적으로 필요한 공간을 말한다.
좋은 알고리즘은 시간도 적게 걸리고 자원의 사용도 적어야 한다. 다만 시간과 공간은 반비례적인 경향이 있어 선택의 문제가 되는 경우도 있을 수 있다. 이 때 알고리즘의 척도는 시간 복잡도를 위주로 판단하는 편이다.
📌 참조
frontend developer 📚