알고리즘 시간복잡도에 대해

목차

Complexity

Up & Down 게임을 해봅시다!

1~100까지의 숫자 중 하나를 생각해보겠습니다. 전 96을 생각할껍니다.
이걸 누군가에게 맞춰보라고 하고, up & down으로 대답하겠습니다.

 

"1" ⇒ up
"2" ⇒ up
"3" ⇒ up
.. (92번을 더 한 후)
"96" ⇒ 맞았..어..

이렇게 물어볼사람은 없을껍니다! 다들 자연스럽게 아래와 같이 물어볼꺼에요.

 

"50" ⇒ up
"75" ⇒ up
"87" ⇒ up
"93" ⇒ up
"96" ⇒ 맞았어!

  이걸 다르게 표현해보겠습니다. 우선 1부터 차례대로 물어본 전자의 경우를 보겠습니다.
1~100까지의 100개를 N개라 표현하겠습니다. 이 경우 만약 생각한 숫자가 100이라면(= 생각한 숫자가 N이라면) 최악의 경우로, 100번 물어봐야 합니다(=N번 물어봐야 합니다.)
이걸 앞에 'O'를 붙여 아래와 같이 표현하겠습니다.

 

  그럼 절반씩 나누어가며 물어본 후자의 경우는 어떻게 될까요?
2로 계속 나누어가며 물어보니 N개에 대해 아래와 같이 표현할 수 있습니다.

 

  이 경우, N이 100개라면 전자는 최대 100번, 후자는 최대 7번만(2^7 = 128) 물어보면 up & down 게임을 끝마칠 수 있습니다.

 

 

시간 복잡도

  위와 같이 질문에 따라 결과를 얻기까지 어느정도의 시간이 걸릴 지 미리 생각해볼 수 있습니다. 프로그램적으로 얘기하자면, 입력값의 크기(N)에 대해 프로그램이 '대강' 몇 번의 연산이 필요할지, 즉 시간이 얼마나 걸릴 지 미리 알아볼 수 있습니다.

  그리고 당연히 시간이 빠를수록 좋겠죠! UP & DOWN 게임을 할 때 누구나 당연하게도 1번부터 100번까지 차례대로 부르지 않고 계속 중간 숫자를 계속 부르듯이요.
⇒ 이걸 '시간 복잡도'라고 부릅니다.

 

  그렇다고 정확하게 몇 번인지 세보지는 않습니다. big-O 표현법의 경우 최악의 경우를 나타내며, 그 중에서도 가장 큰 영향을 주는 항만 '대충' 계산합니다. 결국 N이 커질수록 나머지 값은 영향이 미미해지거든요.

• big-O(오) 표현법 : 최악의 경우
• big-θ(세타) 표현법 : 평균의 경우
• big-Ω(오메가) 표현법 : 최상의 경우

 

  가장 큰 영향을 주는 항만 계산한다는 말은 예를들어 아래와 같습니다.

 

 

대표적인 시간 복잡도 표현

  대표적으로 나타내는 몇가지 시간복잡도 표현에 대해 어느정도 차이가 나는지 그래프로 보겠습니다.

( https://www.desmos.com/calculator?lang=ko 에서 직접 그려보실 수 있어요!)

 

N이 100정도만 되도 엄청난 차이가 나게됩니다.

• O(1) : 약 1번
• O(logN) : 약 2번
• O(N) : 약 100번
• O(N^2) : 약 10,000번
• O(N^3) : 약 1,000,000번
• O(N!) :

 

  따라서 N^3 + N^2 + N 이런걸 해도 N이 100만되도 N^2과 N은 의미가 크게 없는걸 알 수 있습니다. 그래서 가장 큰 영향을 주는 항 위주로 표현합니다.

 

 

공간 복잡도

  복잡도에는 위에서 말한 시간복잡도 외에 공간복잡도도 마찬가지 방식으로 표현합니다. 데이터 N개에 대해 해당 프로그램에서 어느정도의 공간(메모리)를 잡아먹는지 표현하는 용도입니다. 다만 요즘 메모리가 워낙 커서 메모리가 작을수록 단가를 줄일 수 있는 작은 임베디드 시스템같은게 아니라면 크게 따지지 않는걸로 알고있습니다.

 

  대부분의 경우 시간과 메모리는 trade-off 관계입니다. 메모리를 더 쓰면 시간을 줄일 수 있는 경우가 많습니다.

 

 

PS에서의 시간복잡도

  예를들어 자연수 N을 입력받아 1부터 N (N은 최대 10억)까지 모든 자연수를 더한값을 출력하는 프로그램(시간제한 : 1초)을 짠다고 보겠습니다. 이 때 단순하게 아래와 같이 짜보겠습니다.

...
long sum = 0l;
for (long i = 0; i < N; i++) {
    sum += i;
}
...

• 위 프로그램은 N에 대해 N번 동작하니 O(N)이 됩니다. 이 때, N은 최악의 경우 10억이므로 대강 최대 10억번의 연산이 필요합니다. 컴퓨터 사양에 따라 다를 수 있으나, 대강 컴퓨터의 연산속도를 계산할 때 1억번의 단순연산(덧셈,뺄셈같은)을 1초로 잡습니다. 따라서 위의 경우 10초정도가 걸린다고 생각할 수 있겠습니다. 시간제한은 1초이므로 애초에 이 방법으로는 풀 수 없다는것을 파악할 수 있습니다.

 

  그러니 이번엔 다른 방법을 생각해보겠습니다. 1부터 N까지 1씩 차이가 나는 등차수열의 합이므로, 등차수열의 합을 구하는 공식을 사용하면 한 번에 구할 수 있습니다.

...
long sum = N * (N+1) / 2;
...

• 이 경우 한방에 계산결과가 나오니 O(1)이 되며, 시간 제한 1초 내에 위에서 짜려고 했던 10초짜리 연산과 동일한 결과를 낼 수 있습니다.

 

 

프로젝트에서의 시간복잡도

  이러한 복잡도 계산은 실제 일을 할때도 도움이 될 수 있습니다. 이번엔 좀 더 실제 프로젝트 시 있을만한 예시를 들어 보겠습니다.

 

  배관에 대해 배관 번호(PK)를 기준으로 배관 길이를 가지고 있는 데이터가 있습니다. 배관 10만개 정도의 데이터를 가지고 있다고 보겠습니다.

• [ {배관번호:123, 배관길이:11}, ...(10만개) ]

 

  그런데 10만개의 배관에 대해 이번엔 배관색상 정보를 가진 또다른 데이터가 있습니다.

• [ {배관번호:123, 배관색상:"red"}, ...(10만개) ]

 

  문제는 화면상에 리스트로 모든 배관의 정보를 보여줘야하는데 위 두 데이터를 하나로 합쳐서 배관길이와 배관색상을 둘 다 보여줘야 합니다. 즉, 다음과 같이 보여져야 합니다.

• "배관길이 : 123 / 배관길이 : 11 / 배관색상 : red"
• ... (10만개)

 

  이 경우 일반적으로 생각할 수 있는 방법대로 for문을 2번 중첩해서 동일한 배관번호를 기준으로 데이터를 합칠 경우 ⇒ 첫번째 배열 순회하는데 O(N), 첫번째 배열의 각 값에 대해 두번째 배열을 순회하는데 O(N)이므로 O(N x N) = O(N^2) ⇒ 10만 x 10만 = 100억 ⇒ 약 100초 가 걸립니다.

 

  하지만 메모리를 좀 더 써서, 첫번째 배열을 순회하며 HashMap에 key-value 쌍을 맞춰두는 전처리를 해두면, 두번째 배열을 순회하며 key를 기준으로 바로바로 찾을 수 있습니다.

  이 경우 첫번째 배열을 HashMap으로 변경하는 시간이 O(N)이 걸리고, 두번째 배열을 순회하는데 O(N), 그리고 찾는데 O(1)이 걸리므로 최종적으로 ⇒ O(N+Nx1)으로 0.1초도 안걸립니다.

 

  이하 사족이지만, 위의 경우는 DB를 거치지 않고 프로그램상에서 동작하는 경우를 예시로 들었습니다만, 물론 일반적으로는 위와 같은 경우 DB에서 배관번호에 대해 인덱스를 걸고 join이나 select-where를 수행할 것입니다.

• DB에 인덱스를 거는 것이 결국 위에서 HashMap으로 전처리를 했던 것과 같이 모든 경우를 보지 않고, 더 빠르게 동작할 수 있는 알고리즘을 수행할 수 있도록 메모리를 더 써서 전처리를 해두는 것입니다.
• DB 인덱스는 일반적으로 Balanced Tree를 사용해 데이터를 저장해두는데(인덱스 걸 때 선택하는 방식에 따라 다름), 이 경우 위보다 느린 퍼포먼스를 보여줍니다. Balanced Tree에서 데이터 탐색이 O(logN)이므로, 최종적으로 O(NlogN) ⇒ 대략 0.1초~1초정도
• 위처럼 더 빠른 HashMap을 사용하지 않고 B-Tree로 전처리 해두는 이유는 DB에서는 부등호로 검색하는 경우도 있기 때문입니다. 즉, SELECT의 WHERE문으로 인덱스 걸린 배관번호가 50보다 큰걸 전부 뽑아라! 이러면 정렬이 안된 HashMap보다 B-Tree로 전처리 해두는게 더 이득입니다. 비슷하게, 접근도 빠르고 정렬도 시켜둘 수 있는 배열로 전처리를 안해두는 이유는 DELETE 연산 시 인덱스를 배열로 전처리를 해두면 DELETE시에 엄청난 시간이 걸리기 때문입니다. (B-Tree는 삽입, 삭제, 탐색 모두 O(logN))
• O(logN)도 충분히 빠른 알고리즘에 속하기 때문에 평균적으로 가장 성능이 좋은걸로 해두는거죠.