Concept: 시간복잡도의 기본적인 이해

시간복잡도Time Complexity의 기본적인 이해

이 글에서는 시간복잡도의 대표적인 유형과 기본적인 원리에 대해 이해해봅니다. 시간복잡도가 왜 낮아야 좋은 건지, 내가 짠 코드가 어떤 시간복잡도에 해당하는지는 알고 있도록 돕는 글입니다. 이 글을 읽어도 시간복잡도를 증명하거나 하는 일은 할 수 없습니다. 그 정도의 개념을 설명하고 있어요.

시간복잡도란?

---

시간복잡도는 매-------------------우!!!!!! 큰 수의 데이터 표본을 다룰 때에 좀 더 효과적으로 처리하고자 고안된 개념이에요.

시간복잡도 표기와 읽기

---

O(1), O(n)과 같은 식으로, 대문자 O 옆에 괄호를 쓰고, 그 안에 복잡도를 기록하는 식으로 표기합니다. 이 표기법을 빅오 표기법이라고 해요.
각각 오원, 오엔의 시간복잡도를 갖는다고 말합니다.

먼저 O(1), O(n)에 대해서 알아보자

---

배열이 있습니다.

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

• 이 배열의 [0]에 접근할 때는, 0이라는 인덱스(주소)를 갖고서 곧바로 접근하는 것이죠. 한 번(1)에 갈 수 있습니다. 이걸 O(1)의 시간복잡도라고 말해요.

• 이 배열의 [n]에 접근할 때는, n이라는 인덱스를 갖고서 곧바로 접근합니다. 역시 한 번에 갈 수 있습니다. 이것도 O(1)의 시간복잡도를 갖는다고 말해요.

• 이번에는 이 배열의 [0]를 3번 호출한다고 해볼게요. 한 번에 접근하는 것을, 3번 반복하는 거잖아요? 그러니까 일단 O(3)으로 표기해볼게요.

  • 하지만 시간복잡도 표기 안에서 상수는 별 의미가 없습니다. 왜냐면, 앞에서 시간복잡도는 상대적으로 매---우!!! 큰 단위의 데이터 표본을 다루기 위한 거라고 했잖아요? 100000000...000가 등장할 수 있는데 그 옆에 1이 있든 3이 있든 100이 있든 별 의미가 없겠죠. 그래서 상수는, 그냥 상수라고만 말합니다. 편의상 1로 퉁쳐서 표기해요.
  • 그래서 [0]를 3번 호출하는 코드, 위에서 O(3)라고 적어놓은 코드도 O(1)의 시간복잡도에요. 상수 만큼의 시간이 걸린다고 해서 '상수시간이 걸리는 코드'다 라고 말하기도 합니다.

• 이제 인덱스를 모른다고 가정해봅시다. 요소값이 n인 배열방을 찾고 싶어요. 그러면 배열을 앞에서부터 쭉 훑으면서 값이 n인 것을 찾아야겠죠?

0번 인덱스의 값은 0이었다.
1번 인덱스의 값은 1이었다.
2번 인덱스의 값은 2였다.
3번 인덱스의 값은 3이었다.
4번 인덱스의 값은...
...
n-1번 인덱스의 값은 n-1이었다.
n번 인덱스의 값은 n이었다. 찾았다!

• 이렇게 길이가 n인 배열에서 특정 값을 탐색을 할 때는, n만큼의 연산이 필요했습니다. n번의 연산! 이것은 O(n)이라고 표기할 수 있어요. 크기 n의 자료구조를 선형적으로 쭉 탐색하는 데에 걸리는 시간이라서, 선형시간이라고 부르기도 해요.

O(n^2), O(n^3)

---

• 이번에는 배열에서 값이 n인 값을 찾을 거에요. 그리고 값 n인 요소가 존재하면, 그 요소에 곱하기 2한 값이 존재하는지 찾아서, 존재하면 true를 리턴해줄게요.

for (int i  = 0; i < arr.length; i++) {
    if (arr[i] == n) {
        for (int j = 0; j < arr.length; j++) {
            if (arr[i] == n * 2) {
                return true;
            }
        }
    }
}

이렇게 코드를 짜는 분은 없으실 거라고 생각하지만... 설명을 위해 이렇게 짜봤어요. 이렇게 짜도 위의 설명과 같이 동작하잖아요?
그래서 코드를 살펴보면, 바깥쪽 for문을 돌면서 O(n) 만큼의 시간이 소요되어요.
그런데! O(n)의 로직을 수행하고 있는 안쪽에서 매번 O(n)의 로직을 수행하는 안쪽 for문이 발견되었네요!
n번을 한번씩 수행할 때마다, n번의 작업을 수행한다. n^2(제곱)번의 작업이 수행되겠죠?
이 코드의 시간복잡도는 O(n^2)입니다.

그럼 만약 이렇다면요?

for (int x = 0; x < arr.length; x++) {
    for (int y = 0; y < arr.length; y++) {
        for (int z = 0; z < arr.length; z++) {
            // do something...
        }
    }
}

길이가 n인 arr를 탐색하는 작업을 세제곱 만큼으로 수행합니다. O(n^3)의 시간복잡도가 걸립니다.
n의 데이터 표본수가 100이면? 1,000,000번이나 수행되죠? 10000만 되어도? 어휴... 이런 코드는 반드시 개선해야겠다는 걸 바로 알 수 있네요.

O(log n)

---

"아... 수학 모르는데"라고 생각하셔도 괜찮습니다. 저도 수학 몰라요. log가 뭔지 까먹은 지도 10년이 넘은 것 같네요.
하지만 대강 개념만 아시면 됩니다. 시간복잡도를 증명할거면 몰라도, 이용할 거라면 컨셉만 알고 있으면 되어요.

log란 제곱(지수)의 역입니다. 시간복잡도의 표기에서 log n은, log와 n 사이에 작게 써놓은 숫자 2가 생략된 거거든요?(때론 3이나 4일수도 있지만 여튼 생략된...) 2가 n이 되려면 몇 제곱을 해야하는지를 표시하는 거에요. 헷갈리죠? 그래서 최소한 아래와 같이만이라도 이해하고 있으면 될 것 같아요.

n제곱은 n에 매번 2만큼을 곱해나가죠? (^2, 제곱이니까)
log n은 매번 2만큼씩 나눠나가는 거에요.

값들을 배열이 아니라 바이너리 서치 트리 구조로 갖고 있다고 해볼게요.

        4
    2       6
1      3 5      7

모든 부모 노드 밑에는, 부모 보다 작은 값을 가지는 노드가 왼쪽, 큰 값은 오른쪽에 있는 규칙이 있어요.
* 이 BST에서 3을 찾고 싶어요.
* 그러면 루트에서 오른쪽은 버려요. 왼쪽만 남아요. 그러면 둘로 나눠진거죠?
* 왼쪽 노드를 또 반으로 나눠요. 이번에는 큰쪽, 오른쪽만 남겨요. 둘로 나눠진 걸 택했죠?
* 또 나누...려고 했는데 3을 찾았네요. 끝!
이렇게 한 레벨/한 루프를 거칠 때마다 값을 반씩 뚝뚝 떼어버리는 알고리즘을 O(log n)의 시간복잡도가 걸린다고 하는 거에요.
이제 저희도 어디 가서 "BST에서 한 요소를 탐색하는 데에 걸리는 시간은 log n이야"라고 개발자 같은 소리를 할 수 있게 되었네요! 하지만 친구가 없어질 수 있으니 그런 이야기는 하지 마세요!

조합하기

---

만약에 정렬되지 않은 BT를, 잘 정렬해서 BST로 만들어놓고 싶다고 해볼게요.

        1
    5       7
6     4  2     3
...    ...    ...n

이럴 때는 이런 작업을 거칠 거에요.
* 1을 찾고 / 아직 처음이니까 비교할 값이 없어서 일단 루트에 놓을 거에요.
* 2를 찾고 / 이전값과 큰지 작은지 비교해서 왼쪽 혹은 오른쪽에 배치할 거에요.
* 3을 찾고 / 비교해서 배치할 거에요
* 4를 찾고 / 비교해서 배치할 거에요
* 5를 찾고 / 비교해서....
* n을 찾고 / 비교해서 배치할 거에요.
바이너리 트리에 재배치 할 자리를 찾는 작업은 위에서 보았듯이 log n의 시간이 걸리는 작업이에요. 그 작업을 1에서부터 n까지, 총 n번 반복했어요.
다시 말해, 작업이 n 곱하기 log n번 발생했어요.

바이너리를 이용해서 값을 정렬하는 작업은 O(n log n)의 시간복잡도를 가집니다.
다른 많은 정렬 알고리즘들도 이와 같은 시간복잡도를 가지고 있어요(그래서 늘 똑같은 시간이 걸린다는 건 아니에요).

또 이런 경우가 있어요.
길이가 n인 배열만큼 순회하면서, k인 배열에서 탐색하며 일치하는 값을 어떻게 어떻게 조작하는 코드가 있다고 해볼게요.
n만큼 k번 조작해요.
이런 코드의 시간복잡도는 O(n·k)라고 할 수 있어요. 꼭 n만 들어가란 법은 없다는 것이죠!

마무리

---

시간복잡도에 대해서 대략의 감이라도 생기셨나요?
가장 앞서서도 말씀드렸지만 시간복잡도는 절대적인 개념이 아니에요. 그래서 nlogn의 알고리즘보다 n^2의 알고리즘이 항상 느리다고 말할 수는 없습니다. 모든 경우에 대해 최적인 해결책이 존재하지 않기 때문이에요.

"그런데 왜 그런걸 알고 있어야 돼? 어차피 정확하지도 않은거."

하지만 보편적인 경우에 우리가 더 빠르게 동작하는 코드를 수립할 기준이 되어주기엔 충분해요. 또한 시간복잡도 개념을 알고 있어야, 어떤 케이스에서 n^2 알고리즘이 nlogn의 알고리즘보다 빠를 수 있는지 알 수도 있는 거겠죠?

다 함께 다양한 알고리즘 케이스들을 실제로 접하면서 시간복잡도 개념의 활용에 익숙해지기를 바랍니다. 감사합니다.