알고리즘 복잡도

이것이 코테다를 읽고 정리한 내용

복잡도는 알고리즘의 성능을 나타내는 척도이며 시간 복잡도와 공간 복잡도로 나뉩니다.

• 시간 복잡도: 문제 해결을 위해 필요한 연산의 횟수
• 공간 복잡도: 문제 해결을 위해 필요한 메모리의 양

동일한 기능을 수행하는 알고리즘이라면 복잡도가 낮을 수록 더 좋다고 할 수 있습니다.

 

시간 복잡도

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용합니다.

빅오 표기법은 간단히 말해서 가장 빠르게 증가하는 항만 고려한 표기법입니다.

 

O(N)

int[] array = {3, 5, 1, 2, 4};
int sum = 0;	

for (int i : array) {
    sum += i;
}

배열의 값을 한번씩 조회해서 더하는 예제입니다.

위 예제에서 연산 횟수는 배열의 길이에 비례하므로 시간 복잡도는 O(N)이라고 할 수 있습니다.

 

O(1)

int a = 5;
int b = 3;
int result = a + b;

위 예제의 연산 횟수는 단 1입니다. 때문에 시간 복잡도는 O(1)로 표현할 수 있습니다.

 

O(N²)

int[] array = {3, 5, 1, 2, 4};

for (int i : array) {
    for (int j : array) {
        System.out.println(i * j);
    }
}

이중 반복문을 통해 N개의 데이터를 N번 연산하는 예제입니다. 따라서 시간 복잡도는 O(N²)입니다.

 

빅오 표기법과 명칭

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

문제 유형에 따른 알고리즘 선택 예시

• N의 범위가 500: O(N³)
• N의 범위가 2,000: O(N²)
• N의 범위가 100,000: O(NlogN)
• N의 범위가 10,000,000: O(N)

공간 복잡도

공간 복잡도 또한 빅오 표기법으로 표현합니다. 보통 문제에 메모리 제한이 걸려있는 데 공간 복잡도를 제한하기 위함입니다.