[알고리즘] 복잡도 (시간 복잡도, 공간 복잡도)

mallin·2022년 2월 22일

algorithm

알고리즘

목록 보기

6/9

복잡도는 알고리즘의 성능을 나타내는 척도로, 시간 복잡도와 공간 복잡도로 나눌 수 있습니다.

⏰ 시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지

시간 복잡도를 통해 알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있습니다.

알고리즘 문제를 풀 때 단순히 '복잡도' 라고 하는 경우엔 보통 시간 복잡도를 의미합니다.

시간 복잡도를 표현할 때에는 빅오(Big-O) 표기법을 사용합니다.
빅오 표기법을 간단하게 표현하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다. 함수의 상한만을 나타냅니다.
즉, 3N3 + 5N2 + 1000000 일 때 차수가 가장 큰 O(N3) 으로만 표기됩니다.

EX) N 개의 배열 값을 모두 더해 결과를 출력하는 프로그램

N 개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 만든다고 가정하겠습니다. 이런 경우 우리는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하며 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있습니다. 다음처럼요.

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

 	for (int i=0;i<arr.length;i++) {
 	 	sum += arr[i];
 	}
 	System.out.println(sum);

해당 코드에서는 N 의 개수에 따라서 연산 횟수가 달리지기 때문에
시간복잡도는 O(N) 입니다.

EX2) a+b 의 값을 출력하는 프로그램

int a = 5;
int b = 7;
System.out.println(a+b);

이번 코드는 a와 b 의 값을 단순히 더하는 코드로 굉장히 간단합니다.
여기선 단순 더하기 연산 한번만 수행되고, 이는 상수 연산 이기 때문에
시간 복잡도는 O(1) 입니다.

EX3) 2중 반복문

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

for (int i=0;i<arr.length;i++) {
    for(int j=0;j<arr.length;j++) {
        System.out.println(arr[i]*arr[j]);
    }
}

2중 반복문을 이용해 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 출력하는 코드입니다. N x N 만큼의 연산이 필요하다는 걸 유추할 수 있습니다. 그렇기 때문에
시간 복잡도는 O(N2) 입니다.

하지만, 모든 2중 반복문의 시간 복잡도가 O(N2) 가 아니기 때문에 소스 코드를 정확히 분석한 후 시간 복잡도를 계산해야한 다는 점을 기억해주세요.

시간 복잡도 표

빅오 표기법	명칭	N이 1,000일 때의 연산 횟수
O(1)	상수 시간 (Constant time)	1
O(logN)	로그 시간 (Log time)
O(N)	선형 시간	1,000
O(NlogN)	로그 선형 시간	10,000
O(n2)	이차 시간	1,000,000
O(n3)	삼차 시간	1,000,000,000
O(2n)	지수 시간