시간 복잡도, 공간 복잡도 그리고 빅 오 표기법 (Big-O Notation)
시간 복잡도, 공간 복잡도이란
시간 복잡도와 공간 복잡도는 작성한 코드(알고리즘)가 얼마나 효율적인가를 알려주는 척도이다.
시간 복잡도는 작성한 알고리즘의 수행 시간(횟수)이 얼마인지를 나타내는 척도이다.
공간 복잡도는 작성한 알고리즘이 얼마만큼의 메모리 공간을 사용하고 있는가를 나타내는 척도이다.
시간 복잡도란 big-O에 대한 시간 개념으로 알고리즘의 수행 시간이 얼마인지를 나타냅니다. 수행되는 연산의 수를 가지고 계산하며 알고리즘에서 중요하지 않는 값들은 최대한 무시합니다.
빅오(Big-O) 표기법이란
앞서 말한 시간 복잡도와 공간 복잡도를 수학적으로 표시하는 대표적인 방법이 빅오이다. 빅오를 표기하는 데에 2가지의 규칙이 적용된다.
1. 가장 높은 차수만 남기기.
O(n³+n²) -> O(n³ )
2. 계수와 상수는 제거 (단, 상수만 있을 경우는 제거 X)
O(3n²+2) -> O(n² )
빅오 표기법으로 보는 시간 복잡도
-
O(1) 상수 - (Constant)
입력받는 데이터의 크기와 관계없이 항상 일정한 시간이 걸리는 알고리즘임을 의미한다. 데이터의 증가가 성능에 영향을 거의 주지 않는다.
-
O(log n) 로그 - (Logarithmic)
입력받는 데이터의 크기가 커져도 처리되는 시간이 늘어나지 않고, 점차 줄어드는 알고리즘이다. 대표적인 예로 이진 탐색 알고리즘이 있다.
-
O(n) 선형 - (Linear)
입력받는 데이터의 크기에 비례하여 처리되는 시간이 증가하는 알고리즘이다. 대표적인 예로 선형 탐색 알고리즘이 있다.
-
O(nlog n) 로그 선형 - (Linear)
입력받는 데이터의 크기에 비례하여 처리되는 시간이 선형일 때 보다 조금 더 증가하지만 급격하게 증가는 하지 않는 알고리즘이다. 대표적인 예로 퀵 정렬, 병합 정렬, 힙 정렬 알고리즘이 해당된다.
-
O(n²) 이차 - (Quadratic)
입력받는 데이터가 커지면 커질수록 처리되는 시간이 급격하게 늘어나는 알고리즘이다.
대표적으로 이중 루프 알고리즘에 해당하며, n² matrix 형태가 된다. 단, 이중 루프에서 m이 n보다 작을 경우 반드시 O(nm)으로 표시해야 한다. -
O(2ⁿ) 지수 - (Exponential)
입력받는 데이터가 커지면 커질수록 처리되는 시간이 기하급수적으로 늘어나는 알고리즘이다. 대표적인 예로 피보나치 수열이 여기 해당된다.
-
O(n!) 팩토리얼 - (Factorial)
입력받는 데이터가 커지면 커질수록 처리되는 시간이 초기하급수적으로 늘어나는 알고리즘이다.
복잡도는 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)로 뒤로 갈수록 복잡해진다.
입력받는 데이터 크기(n)에 대한 O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)를 비교하면, 다음 표와 같이 나타난다.
