[01] big-O :: 코딩 인터뷰 완전 분석

점근적 실행 시간(asymptotic runtime), big-O

 

 

[시간 복잡도]

파일을 전송한다고 할 때,

O(s),

온라인 전송을 한다고 하면, s는 파일의 크기가 된다.

파일의 크기가 증가함에 따라 전송 시간 또한 증가한다.

 

하지만 직접 전달(비행기, 자동차 등)을 이용한다면 파일 크기에 상관 없이 O(1)(상수)일 것이다.

파일의 크기가 증가한다고 해서 파일을 전송하는데 걸리는 시간이 늘어나지 않는다.

 

big(O) 수행시간을 크게 세 가지로 나눠서 표기할 수 있다.

1. O(big-O)

시간의 상한을 나타낸다.

O(N)으로 표기하지만, N보다 큰 숫자도 표현할 수 있다.

O(N^2), O(N^3), O(2^N) 등으로도 표현할 수 있다.

이는 O(N)보다 큰 어떤 수행 시간으로도 표현이 가능하다.

 

2. Ω(big-Omega)

등가개념 혹은 하한을 나타낸다.

Ω는 등가 개념 혹은 하한을 나타낸다.

알고리즘은 Ω(N) 뿐만 아니라 Ω(logN) 혹은 Ω(1)로도 표현할 수 있다.

결국, 해당 알고리즘은 Ω 수행시간보다 빠를 수 없게 된다.

 

3. θ(big theta)

θ는 O와 Ω 둘 다를 의미한다.

 

 

퀵 정렬의 경우

구현 방식에 따라 조금 달라질 수 있지만

 

모든 원소가 동일하다면 평균적으로 단순히 배열을 한 차례 순회하고 끝날 것이다. (최선의 경우)

 

만약 배열에서 가장 큰 원소가 계속해서 축이 된다면 수행 시간은 O(N^2)가 된다. (최악의 경우)

 

하지만 평균적인 경우에는 O(NlogN)이다.

 

 

최선의 경우에는 시간 복잡도를 논의하지 않는다.

 

 

[공간 복잡도]

알고리즘에서는 시간 뿐만 아니라 메모리(혹은 공간)도 신경써야 한다.

시간 복잡도와 거의 동일하다고 볼 수 있다.

 

크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다.

크기가 nxn인 배열을 만들고자 한다면, O(n^2)의 공간이 필요하다.

 

재귀 호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함된다.

int sum(int n) {
	if (n <= 0) {
    	return 0;
       }
       return n + sum(n-1);
}

호출될 때마다 스택의 깊이는 깊어지게 된다.

이 호출은 전부 호출 스택에 더해지고 실제 메모리 공간을 잡아먹게 된다.

 

int PairSumSeq(int n){
	int sum = 0;
    for (int i = 0; i < n; i++){
    	sum += pairSum(i, i+1);
       }
 }
 
 int PairSum(int a, int b){
 	return a+b;
}

위의 코드는 함수를 O(n)번 호출했지만,

함수들이 호출 스택에 동시에 존재하지 않으므로 O(1) 공간만 사용

 

 

1.

big-O를 사용할 때, 상수항은 무시해버린다.

O(2N)인 상황에서도 O(N)으로 표기한다.

 

2.

최고차항이 아닌 항은 무시해도 된다.

O(2N^2) = O(N^2+N^2) = O(N^2)

여기서, N^2이 무시되게 된다.

O(N^2 + N)의 경우에는 N^2보다 작은 N항도 무시하게 된다.

즉, O(N^2 + N) = O(N^2) 이 된다.

 

하지만, O(B^2+A)의 경우에는 하나의 항으로 줄일 수 없다.

 

 

[덧셈 수행 시간, 곱셈 수행 시간]

만약 알고리즘이 A를 끝마친 후 B를 수행해라의 경우 A와 B의 수행 시간을 더해야 한다.

만약 알고리즘이 A를 할 때마다 B를 수행하라의 경우 A와 B의 수행 시간을 곱해야 한다.

 

 

[O(logN) 수행시간]

이진 탐색의 경우, 원소 x와 배열의 중간 값을 계속 비교하기 때문에, 

 

만약 원소가 8개인 배열의 경우,

N = 8

N = 4 (8/2)

N = 2 (4/2)

N = 1 (2/1) 이 된다.

 

뒤집어서 보면, 1에서 8로 증가하는 순서로 생각해보면, 숫자 1에 2를 3번 곱해야 8이 된다.

 

2^k = N 을 만족하는 k를 구할 때 사용되는 개념이 log이다.

 

2^3 = 8   =>   log2_8 = 3