Big-0 표기법
빅오 표기법은 수리과학 분야에서 특정 함수의 증감 추세를 비교하는 표기법으로, 아래와 같은 형식으로 복잡도를 표현합니다.
O(n), O(n log n)
이 표기법은 알고르즘의 성능을 평가하는데도 자주 사용됩니다.
알고리즘의 성능은 시간복잡도와 공간복잡도를 기준으로 효율적인지 비효율적인지 평가합니다.
시간복잡도
시간복잡도는 간단히 말해서, 연산 횟수라고 볼 수 있습니다.
위는 여러 알고리즘의 시간복잡도를 빅오 표기법으로 표현하여 복잡도가 증가하는 속도를 비교한 그래프 입니다.
가로축은 확인해야할 경우의 수(Elements), 세로축은 연산 횟수(Operations)인데요.
확인해야할 경우의 수를 n이라고 가정했을때, 각 알고리즘별 복잡도 증가 횟수를 알 수 있습니다.
가장 최악의 복잡도를 자랑하는 O(n!), O(2^n), O(n^2) 등등은 최대한 사용을 피해야 하는 알고리즘입니다.
public class Solution {
private final int MY_NUM = 2;
public void solution(int n) {
int[][] numbers = new int[n][n];
for(int i=0; i<numbers.length; i++) {
for(int j=0; j<numbers[0].length; j++) {
numbers[i][j] = MY_NUM + i + j;
}
}
}
}위 소스코드는 numbers라는 배열에 숫자를 입력하는 로직입니다.
바깥 for문이 n번 반복하고 안의 for문이 다시 n번 반복하는 로직입니다.
이를 빅오 표기법으로 나타내면 위 그래프의 O(n^2)에 해당합니다.
그런데 여기서 시간 복잡도은 연산 횟수라고 했는데, 반복문 안의 덧셈과 같은 세부적인 연산은 왜 표기하지 않을까요?
그건 바로 시간 복잡도를 표기할 때는, 상수를 모두 제거하기 때문입니다.
더하기 연산을 포함하면 O(2n^2)라고 표현할 수도 있지만, 시간복잡도를 표현할 때는 상수를 모두 제거하고
O(n^2)로 표기합니다.
코딩할때 별 생각없이 흔히 사용하는 이중 반복문은 보시다시피 시간복잡도가 매우 높은 로직입니다.
만약 작성한 코드에 이중 반복문이 있다면, 이를 개선할 방법이 있을지 꼭 고민해보시기 바랍니다.
공간 복잡도
공간 복잡도는 특정 알고리즘을 실행하는데 얼마만큼의 메모리가 사용되는지 측정한 복잡도 입니다.
이 공간 복잡도를 다시 고정 공간과 가변 공간으로 나누어 생각해볼 수 있습니다.
고정 공간은 단순 변수와 상수가 저장되는 공간으로 생각할 수 있습니다.
가변 공간은 로직이 실행되며, 런타임에 동적으로 사용되는 공간으로 생각할 수 있습니다.
public class Solution {
private final int MY_NUM = 2;
public void solution(int n) {
int[][] numbers = new int[n][n];
for(int i=0; i<numbers.length; i++) {
for(int j=0; j<numbers[0].length; j++) {
numbers[i][j] = MY_NUM + i + j;
}
}
}
}위와 같은 로직이 있다고 가정할 때, 고정 공간에 해당하는 것들은 다음과 같습니다.
- Solution class 변수 MY_NUM -> 4byte
- solution method 파라미터 n -> 4byte
그리고 가변 공간은 다음과 같습니다.
- n * n * 4byte -> n^2 * 4byte
(inputNumbers의 길이를 n으로 가정)
만약 n의 값이 100,000 이라면 40,000,000,000byte의 가변 공간을 사용하게 됩니다.
이 예시를 보면 우리는 알고리즘을 작성할 때, 가변 공간에 집중해야한다는 것을 알 수 있습니다.
정리
빅오 표기법이란, 복잡도를 표현할때 주로 사용되는 표기법시간 복잡도란 확인할 경우의 수(n)의 개수에 따른연산 횟수공간 복잡도란 확인할 경우의 수(n)의 개수에 따라 사용되는가변 공간(메모리)