시간 복잡도와 빅오(Big-O) 표기법

🧑‍💻 시간 복잡도란?

---

코드의 실행 시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계입니다.

 

1. 빅오(Big-O) 표기법

1) What? 

코드의 효율성을 검사하는 데 사용하는 시간 복잡도의 대표적인 표기법 중 하나이며,

빅오 표기법은 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 데이터 간의 상관관계를 표기합니다. 예를 들어, 입력 크기가 N이고, 이와 비례하는 시간이 걸리는 알고리즘의 시간 복잡도는 O(N)입니다.

 

2) Example

다음과 같은 코드에서 길이가 N인 배열이 있다고 가정합시다.

private int search(int[] array, int target) {
   for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
     
	return -1;
}

 

이 코드는 평균적으로 배열 중간쯤에서 원소를 찾게 될 것입니다. 하지만, 최악의 경우 모든 원소를 순회한 후 원소를 찾게될 것입니다. 즉, 전체 배열을 순회하므로 O(N) 시간 복잡도를 갖게됩니다.

 

물론 다른 표기법도 있습니다. 하지만, 코딩 테스트에서 효율성을 묻는 문제는 문제 제한 사항에 명시되어 있는 조건을 극한으로 맞추는 입력 데이터를 사용해서 코드를 평가합니다.

따라서, 입력될 수 있는 최악의 상황을 상정하여 시간 복잡도를 계산할 수 있도록 빅오 표기법을 사용하여 알고리즘을 설계하고자 합니다!

 

 

2. 시간 복잡도 그래프

1) 시간 복잡도의 중요성

위에 언급하였듯, 시간 복잡도는 실행 시간과 입력 크기의 상관관계입니다. 입력 크기(N)이 작다면 연산이 적기 떄문에 시간 복잡도가 의미 있는 차이를 만들지 못하지만, 만약 입력 크기가 커진다면 실행 시간의 차이는 무시 못할 정도로 커질 것입니다.

다음은 대표적인 알고리즘의 시간 복잡도입니다.

알고리즘	시간 복잡도
이진 탐색	O(logN)
선형 탐색	O(N)
정렬	O(N*logN)
조합	O(2^N)
순열	O(N!)

 

특별한 로직이 없는 사칙 연산과 같은 단순 연산의 시간 복잡도는 상수 시간이라고 하며, O(1)로 표기합니다.

위 표에서 볼 수 있듯이 흔히 접할 수 있는 알고리즘의 시간 복잡도는 O(1), O(logN), O(N), O(N*logN), O(N^2), O(2^N) 등이 있습니다.

다음 그래프는 시간 복잡도에 따른 입력과 실행 시간의 상관관계를 나타낸 그래프입니다.

 

입력값(N)이 커질수록 시간 복잡도의 결과값 차이는 굉장히 커지는 것을 알 수 있습니다. 이렇듯, 규모가 큰 서비스일수록 효율적인 알고리즘을 사용하여 코드를 짜는 것이 중요함을 알 수 있습니다.

2) 입력 데이터 개수별 시간 복잡도

만약 코딩 테스트에서 1초라는 제한이 있을 때, 어느 정도 시간 복잡도이어야 제한을 만족할 수 있을까요?

문제별로 주어지는 입력 데이터의 종류와 그 개수가 다르기 때문에 정해진 시간 복잡도는 있을 수 없습니다. 하지만, 입력 조건에서 명시되어 있는 최악의 경우를 시간 복잡도에 대입해봤을 때 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높습니다.

 

예를 들어, 문제에서 주어진 제한 시간이 1초이고 N 값이 최대 1만이라고 가정하겠습니다. 시간 복잡도 O(N*logN)에 N을 대입하면 그 값이 약 13만으로 계산되기 때문에 충분히 제한 시간을 만족하는 효율적인 코드라고 할 수 있습니다. 하지만, 시간 복잡도 O(N^2)를 갖는다면 1억이 되기 때문에 시간 제한을 맞추지 못할 가능성이 매우 큽니다.

 

따라서, 자신의 시간 복잡도에 문제의 제한 사항에 표기된 가장 큰 입력을 대입하여 계산했을 때, 아무리커도 1억을 넘기지 않아야 안전한 코드라고 할 수 있습니다.

 

👆 잠깐!!!!

여기서 이야기하는 1억은 절대적인 기준도 아니고, 정확한 실행 시간을 나타내는 것도 아닙니다.
하지만, 일반적으로 코딩 테스트 문제는 시간 복잡도를 이용하여 위와 같은 방법으로 계산했을 때, 대부분 1억보다 한참 아래 값으로 계산되거나 풀이가 잘못돼도 1억을 훨씬 넘는 값으로 계산되기 때문에 일종의 커트라인이라고 할 수 있습니다.
추가로, 당연하겠지만 만약 제한 시간이 3초인 문제가 나오면 3억 번으로 생각할 수 있습니다.

 

 

3. 그래서 효율적인 코드를 작성하는 방법이 뭔데?

풀이를 고안하고 코드까지 작성한 후 시간 초과가 발생한다면 코드마저 새로 작성해야 하는 상황이 발생합니다. 이렇게 되면, 새로운 풀이를 위해 다시 풀이를 고안하고 작성까지 해야하는 상황이 발생합니다.

 

우리에게 시간은 금입니다. 코드를 작성하기 전에 풀이를 먼저 생각하고, 시간 복잡도를 이용하여 효율성이 검증되면 그 이후에 코드를 작성하는 습관을 가집시다!!!!!

 

 

 

 

 

✍️ 시간 복잡도 계산하기

---

이제 ‘시간 복잡도는 어떻게 계산할 수 있을까?’ 라는 의문점을 해소해봅시다!

 

가장 기본이 되는 방법은 반복 횟수를 세어보는 것입니다. 일반적으로 입력되는 값들을 순회하면서 처리하는 데 반복문이 사용됩니다. 이렇게 사용되는 반복문이 어떤 값에 비례하여 반복하는 따져 보면, 시간 복잡도를 계산할 수 있습니다.

 

1. 어림짐작 하기

1) 상수 무시

시간 복잡도는 정확한 시간을 계산하는 것이 아닙니다.
따라서, 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않습니다.

 

예를 들어 길이가 N인 배열의 반만 사용하는 알고리즘이 있습니다. 이는 빅오 표기법 O(N/2)로 나타낼 수 있지만, 상수 부분을 제외하고 O(N)으로 표기합니다.

이와 똑같은 원리로 만약 같은 배열을 두 번 반복하는 경우는 O(2N)를 갖게됩니다. 하지만, 이때 역시 상수 부분을 제외하고 O(N)을 갖게됩니다.

2) M 번 반복

위의 경우는 N 크기의 배열을 상수만큼 반복하는 것이 였습니다.

 

하지만, 배열을 M번 반복해야 한다면, 절대 무시해서는 안됩니다. 이 경우에는 길이 N인 배열을 M번 반복해야 하므로 O(N*M)이 되며, 조건에 맞게 N과 M 모두 최대값을 통해 시간 복잡도를 고려해야 합니다.

// 길이가 N,M 인 배열
int[] arr1 = ... 
int[] arr2 = ...

// 이중 순회
for (int a : arr) {
		for (int b : arr) {
						... 
		}
}

 

3) 순차적 순회

크기 N의 첫 번째 배열을 순회한 후, M 크기의 두 번째 배열을 순회합니다.

 

이 경우에는 N번 반복한 후 M번 반복함으로 O(N+M)으로 표기합니다. 이때도 N과 M의 최대값을 구하여 시간 복잡도에 대입해서 효율성을 판단해야 합니다.

// 길이가 N,M 인 배열
int[] arr1 = ... 
int[] arr2 = ...

// 첫 번째 순회
for (int a : arr) {
		...
}

// 두 번째 순회
for (int b : arr) {
		... 
}

 

 

2. 여러 알고리즘을 이용한 시간 복잡도 계산

하나의 풀이에 여러 알고리즘을 이용할 땐 어떻게 될까요?

아래 코드에서는 크기 N 인 배열을 이중 반복문으로 순회해 O(N^2)의 시간 복잡도가 소요되게 됩니다.

// 길이가 N 인 배열
int[] arr = ... 

// 풀이
for (int a : arr) {
	for (int b : arr) {
			System.out.println(a + " + " + b + " = " + (a + b));
	}
}

 

이 정도까지 읽으셨다면, 밑의 코드는 O(N^2+N) 시간 복잡도가 소요될 것임을 생각할 수 있을 것입니다.

// 길이가 N 인 배열
int[] arr = ... 

// 풀이
for (int v : arr) {
	System.out.println(v + " = " + v);
}

for (int a : arr) {
	for (int b : arr) {
			System.out.println(a + " + " + b + " = " + (a + b));
	}
}

 

하지만 빅오 표기법에서는 실행 시간에 가장 큰 영향을 미치는 항만 표기합니다. 바로 위의 예시에서 N이 커질수록 N^2의 영향력은 N보다 훨씬 커지게 됩니다.

이에 따라 N 은 실행 시간에 무시할 수 있는 영향만 미치게 됩니다. 따라서, 빅오 표기법에서는 가장 영향력이 큰 항만 남겨 O(N^2+N)은 O(N^2)으로 표기됩니다.

 

다음 코드를 봅시다!

// 길이가 N인 배열
int[] arr = ...

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
         int a = arr[i];
         int b = arr[j];

         System.out.println(a + " + " + b + " = " + a + b);
     }
}

 

이 코드에서 안쪽 for문은 전체는 순회하는 것이 아닌, i 값에 따라 순회하는 범위가 정해집니다.

 

i = 0 인 경우, 안쪽 for문은 1~N번 순회를 하고 i = 1 인 경우, 안쪽 for문은 2~N, .. 이런 과정으로 순회하게 됩니다. 따라서, (N-1) + (N-2) + (N-3) + .. + 1번 반복하게 됩니다. 즉, 전체 반복 횟수는 1 부터 N-1까지의 합이 됩니다. 이를 수식으로 표현하면 (N-1)*(N-2)/2가 되며, 다시 한번 풀면 N^2/2 + 3N/2 + 1이 됩니다.

 

이제 O(N^2/2 + 3N/2 + 1)를 풀어써봅시다.

앞서 기재한 것처럼 빅오 표기법에서는 가장 영향력이 큰 항만 표시합니다. 따라서, O(N^2/2 + 3N/2 + 1) = O(N^2/2)가 됩니다.

또한, 상수는 표기하지 않습니다. 즉, 안쪽 for문이 배열 전체를 순회하지 않더라도 O(N^2)으로 표기됨을 알 수 있습니다.

 

 

3. 적절한 알고리즘, 자료구조를 이용한 시간 복잡도 계산하기

효율적인 코드를 작성하기 위해 앞으로 많은 알고리즘과 자료구조를 공부해 볼 것입니다. 같은 문제라도 여러 알고리즘과 자료구조를 이용하면 훨씬 효율적인 코드를 작성할 수 있습니다.

 

예를 들어 정렬된 배열 arr에서 특정 원소를 찾아봅시다. 배열의 모든 원소를 순회하면, O(N)의 시간 복잡도가 소요됩니다. 하지만, 정렬되어 있다는 조건에 이진 탐색을 적용한다면, 시간 복잡도를 O(logN)까지 줄일 수 있습니다.

 

또 다른 예시로, 이번엔 중복을 제거한 배열에서 원소를 찾아봅시다. 이때, 원소 별로 배열 전체를 순회하면 O(N^2)라는 시간 복잡도가 소요됩니다. 하지만, 자료구조 Set을 이용한다면, O(N)로 줄일 수 있습니다.

 

제가 전달하고 싶은건 이진 탐색이 무엇인지, 자료구조 Set은 무엇인지가 아닙니다. 주어진 문제에 맞는 적절한 알고리즘과 자료구조를 이용해 훨씬 효율적인 코드를 짤 수 있다는 것입니다!

 

 

 

---

🗣️ 마치며..

책을 통해 시간 복잡도와 대표적인 시간 복잡도의 표기법 중 하나인 빅오 표기법에 대해서 공부해보았습니다.

이번 공부를 하며 백준 문제를 1년반 동안 풀었지만 매번 문제 풀기 급급해 시간 복잡도를 고려하지 않고 코드만 짰던 제 모습이 매우 부끄러웠습니다ㅠㅎ

 

시간 복잡도의 계산뿐만 아닌, 푸는 과정을 알 수 있었고 무엇보다 앞으로의 알고리즘 문제를 해결하는 과정에 대한 태도를 바꿔야겠다는 다짐을 했습니다.