Big O 란 컴퓨터 공학에서 알고리즘의 성능이나 복잡성을 측정하기 위해 사용되는 개념입니다. 주로 worst 시나리오를 가정하는데, input size가 증가함에 따라 알고리즘의 실행 소요시간(Time Complexity) 또는 메모리나 디스크 상에서 차지하는 공간(Space Complexity)을 나타냅니다. 개념에 대한 설명은 Cracking the Coding Interview의 순서를 따랐습니다.
- 1. Time Complexity
표기는 O(N), O(N^2) 처럼 표시 됩니다. 예를 들어 O(N)이라는 것은 input size에 “선형적”으로 런타임이 비례하는 것입니다.
기울기가 1인 Y = X 라는 그래프를 생각해보았을 때 아래 그래프처럼 선형적인 모양이 생각나실 텐데요, X 값이 증가함에따라 선형적으로 Y 값도 증가하는 것처럼 O(N)도 input N의 크기에 따라 선형적으로 런타임이 증가한다고 이해할 수 있습니다.
- 2. Space Complexity
Space Complexity는 알고리즘이 차지하는 메모리를 나타냅니다. 예를 들어 size가 n인 배열을 생성한다고 하면 O(N) 만큼의 space를 차지한다고 보면 됩니다.
3. Drop the Constants
Big O에서 상수만큼 곱해진 것은 고려하지 않는 것입니다. 예를 들어 O(2N) 으로 보여지는 것도 결국 O(N)과 같습니다.
예를 들어 for loop 하나 안에 if 절 2개가 정의된 것이나 for loop 하나에 if 절 하나, 그 다음 for loop 하나에 if 절 하나인 것이나 같습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.
# O(N)
for loop:
if 절 첫번째
if 절 두번째
# O(2N) 이나 결과적으로 O(N)
for loop:
if 절 첫번째
for loop:
if 절 두번째4. Drop the Non-Dominant Terms
Big O를 계산할 때 큰 영향을 끼치지 않는 것은 제외하는 것입니다. 예를 들어, O(N^2 + N)에서 N은 Big O 계산시에 영향력이 있는 값이 아니기 때문에 N을 제외해서 O(N^2) 으로 나타냅니다. 왜냐면 N이 커지면 커질수록 N을 더하는 것의 영향력은 작아지고 N^2의 영향력이 주요하기 때문입니다.
앞서 살펴본 Drop the Constants 원칙과 비슷한 맥락으로 이해할 수 있습니다.
5. Multi-Part Algorithms: Add + Multiply
만약 알고리즘이 A를 먼저하고 그게 끝나면 그 다음에 B를 하라고 하면 O(A+B)입니다. 반면에 A를 할 때마다 B를 하라고 하면 O(A*B) 입니다. 이러한 로직으로 런타임을 더하거나 곱할 수 있습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.
# O(A+B) --> A 끝나고 B
for loop (A):
for loop (B):
# O(A*B) --> A의 element 마다 B 실행
for loop (A):
for loop (B):6. Amortized Time
Amortized Time 이라는 개념은 worst case가 가끔 발생하지만 한 번 발생하면 한동안은 발생하지 않는다는 것입니다. 예를 들어 array에 element가 추가되다가 어느 순간 capacity에 한계가 오면 새로운 array를 capacity를 double로 해서 생성한다고 할 때, 그 새로운 array에 모든 element를 복제합니다. 이 경우 element를 insertion 하는데 걸리는 런타임을 어떻게 표시할 수 있을까요?
N개의 element를 포함하는 array의 용량이 꽉 차서 사이즈가 2N인 새로운 array로 옮겨갈 경우, 새로 만들어진 array에 기존 element를 추가하는 시간은 O(N)일 것입니다.
그렇지만 이렇게 꽉차서 새로운 array를 생성해서 element를 insert해야하는 상황은 자주 발생하지 않습니다. 따라서 기존에 있던 array에 element를 추가하는 대부분의 insertion하는 시간은 O(1) 입니다.
따라서 어쩌다 한 번 발생하는 worst case의 경우 O(N), 그리고 평균적으로 insertion 하는 case는 O(1) 입니다.
이렇게 size를 증가시키는 배열을 동적 배열 dynamic array 라고 하는데요 좀 더 자세히 살펴보겠습니다. 예를 들어 element가 1개 있을 때 배열이 꽉 찼다라고 보면 이 배열의 사이즈를 2배 늘리는 것입니다. 그러면 사이즈가 원래 1 이었는데 1*2 해서 2로 늘어납니다. 여기서 element가 새로 추가되면서 size 2가 꽉 차게 됩니다. 그러면 size를 2배 늘려서 2*2 = 4 size인 배열이 만들어집니다. 이 상태에서 element 들이 추가되다가 결국 size 4도 꽉 차게 됩니다. 그러면 또 2배 늘려서 size가 8인 배열이 만들어지고 기존에 있던 element들이 이 새로운 사이즈의 배열로 복제됩니다.
이런식으로 계속 기존 배열에 element를 추가하다가 사이즈가 꽉차서 2배만큼 double로 사이즈를 늘리게 되면 공식으로는 1+ 2+ 3+ 8 + 16 + … + X 만큼 런타임이 소요되게 됩니다.
이 수식을 거꾸로 써보면 X + X/2 + X/4 + X/8 + … + 1 이렇게 되는데요 다시 이 공식을 수정하면 X( 1 + 1/2 + 1/4 + 1/8 + …..) = X*(1+1) = 2X 가 됩니다. 1/2 + 1/4 + … 를 다 더하면 이 값이 아래 위키피디아를 참고한 공식에 의해서 총 1이 되기 때문에 다 더하면 2X가 되는 것입니다.
그러면 worst case로 X 만큼 insertion하는 시간은 O(2X) 만큼의 time이 소요됩니다. 여기서 Drop the Constants라는 법칙에 따라서 2를 날려버리게 되면 array 사이즈가 꽉차서 새로 배열을 만들어 기존의 element들을 복제하는데 걸리는 시간은 결과적으로 O(N)이 됩니다.
그러나 이러한 케이스는 드물게 어쩌다 발생하는 것이고, 평소에는 element를 하나씩 추가하기 때문에 O(1) 만큼의 시간이 걸립니다.
7. Log N Runtimes
Binary Search 알고리즘을 통해 Log N 런타임을 이해해보도록 하겠습니다. Binary Search 알고리즘이란 간단하게 말해서 element가 순서대로 sorting이 되어있는 배열에서 원하는 값 x를 찾을 때 배열의 중간에 있는 값과 크기를 비교해서 범위를 축소해나가면서 x를 찾는 알고리즘입니다. 알고리즘의 탐색 범위가 N/2, N/4, N/8 이런식으로 절반씩 줄어들기 때문에 O(log N) 으로 나타낼 수 있습니다. 따라서 탐색 스페이스가 절반씩 줄어드는 알고리즘은 O(log N) 만큼의 complexity를 가진다고 볼 수 있습니다.
예를 들어 [1, 5, 8, 9, 11, 13, 15, 19, 21] 에서 N은 8 >> 4 >> 2 >> 1 이런식으로 탐색 범위가 절반식 줄어든다고 이해할 수 있습니다. 이 순서를 거꾸로 하면 N = 1 >> 2 >> 4 >> 8 이라고 볼 수 있는데 2^3 이 8 이고 log를 씌우면 log 8/log 2 = 3 즉 log N/log 2 = k 여기서 constant인 1/log 2 를 drop 하면 O(log N)이 됩니다.
8. Recursive Runtimes
결론적으로 재귀함수의 space complexity는 O(N) 입니다. 재귀함수는 전체적으로 O(2^N) 만큼의 노드가 있지만 주어진 시간 내에서 차지하는 메모리는 O(N) 입니다.
먼저 재귀함수의 전체 노드를 카운트해 보면 2^0 + 2^1 + 2^2 + … + 2^N 입니다. 수학적으로 다 더하면 2^(N+1) – 1 입니다. 따라서 노드의 수는 O(2^(N+1) – 1) 인데 Constant와 Non Dominant Terms를 제외하면 O(2^N) 이 됩니다. 그러나 주어진 시간에서는 O(N) 만큼의 메모리만 차지합니다. 그 이유는 호출되는 수와 무관하게, 처리되는 것은 depth만큼 누적되기 때문입니다. 예를 들어 다음과 같은 함수가 있을 때,
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1)
}n = 4일 때 f(4) = f(3) + f(3) 인데 여기서 f(3)이 처리되고 순서상 바로 f(2) >> f(1) 까지 순차적으로 처리 되어야만 그 때부터 누적된 것들이 거슬러 올라가면서 처리됩니다. 즉 가장 먼저 처리되는 순서를 보면 f(4) >> f(3) >> f(2) >> f(1) 이기 때문에 depth인 4만큼이 메모리를 차지합니다. 따라서 O(N) 만큼의 space complexity를 차지한다고 볼 수 있습니다.
entheoscientist 