Algorithm
알고리즘의 성능 평가
- 어떤 알고리즘이 있을 때, 알고리즘의 성능을 평가하기 위해 사용하는 척도이다.
- 그 중 시간 복잡도와 공간 복잡도가 있는데, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라고 한다.
- 시간 복잡도 : 특정한 크기의 입력에 대한 알고리즘의 수행 시간 분석
- 공간 복잡도 : 특정한 크기의 입력에 대한 알고리즘의 메모리 사용량 분석
시간 복잡도
- 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미한다.
- 같은 결과를 갖는 프로그래밍도 작성 방법에 따라 걸리는 시간이 다르며, 시간이 적게 걸리는 것이 좋다.
빅-오 표기법
- 시간 복잡도에는 빅-오 표기법이 있다.
- 통전을 튕겨 뒷면이 나올 확률은 첫 번째에 바로 나올 확률도 있지만, 운이 없는 경우에 n번만큼 던져야 하는 경우도 있다.
이 때 n번만큼 던지는 최악의 경우의 수를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다.
- O(1)
- Constant
- 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다.
- 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.
- O(log₂ n)
- Logarithmic
- 입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘이다.
- 예를 들어, 데이터의 크기가 10배가 되면, 처리 시간은 2배가 된다.
- 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우에 해당한다.
- O(n)
- Linear
- 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘이다.
- 예를 들어, 데이터의 크기가 10배가 되면 처리 시간도 10배가 된다.
- 1차원
for문이 있다.
- O(n log₂ n)
- Linear-Logarithmic
- 데이터가 많아질수록 처리시간이 로그 배만큼 늘어나는 알고리즘이다.
- 예를 들어, 데이터의 크기가 10배가 되면 처리 시간은 20배가 된다.
- 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.
- O(n²)
- 데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘이다.
- 예를 들어, 데이터의 크기가 10배가 되면 처리 시간은 최대 100배가 된다.
- 이중 루프가 대표적이며 m이 n보다 작을 때는 반드시 O(nm)으로 표시하는 것이 바람직하다.
- O(2ⁿ)
- 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘이다.
- 피보나치 수열, 재귀가 역기능을 할 경우가 대표적이다.
- O(1)
fast O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slow
1
2
3
4
5
6
7
표기법 예제
O(1) : Push, Pop
O(log n) : 이진트리
O(n) : for 문
O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
O(n²) : 이중 for 문, 삽입정렬, 거품정렬, 선택정렬
O(2ⁿ) : 피보나치 수열
공간 복잡도
- 일반적으로 공간이 하나 생성되는 것을 1이라고 표현한다.
- 이를 O(1)로 표기한다.
- 반복문이 N번만큼 반복해도 for문 안에서의 지역변수이므로 공간 복잡도는 여전히 O(1)이다.
- 다른 것은 전혀 영향을 주지 않는다.
- 재귀함수일 경우
- 함수의 매개변수 n에 따라 공간 복잡도가 달라진다.
- 함수 내부에서 n이 1일 때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간 복잡도는 O(n)이 된다.
공간 복잡도를 줄이는 방법
- 공간 복잡도를 결정하는 것은 보통 배열의 크기가 몇인지, 얼마만큼 동적할당되는지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼친다.
- 프로그램에 필요한 공간은 고정 공간과 가변 공간으로 나뉜다.
- 함수 호출 시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요하다.
- 특히 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이다.