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

big-O 알고리즘 

• 알고리즘의 효율성을 나타내는 지표 혹은 언어. 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는 데 도움이 된다.
• 가장 흔하게 사용되는 예는 O(logN), O(NlogN), O(N), O(N^2) 등이 있다.
• big-O : 학계에서, big-O는 수행 시간의 상한. 해당 알고리즘보다 빠르기만 하면 다 표현 가능하다. (가장 흔히 사용)
• big-Omega : 등가 개념 혹은 하한. 해당 알고리즘은 빅 오메가 수행 시간보다 빠를 수 없게 된다.
• big-theta : O와 omega 둘 다를 의미한다. 
• 상수항은 무시한다. (O(2n) -> O(n))
• 지배적이지 않은 항은 무시하라. (O(n^2+n) -> O(n^2))

 

최선의 경우, 최악의 경우, 평균적인 경우

알고리즘의 수행 시간을 세 가지 다른 방법으로 나타낼 수 있는데, 퀵 정렬로 예시를 들어보자.

quick sort : 축이 되는 원소 하나를 무작위로 뽑은 후, 이보다 작은 원소는 앞에, 큰 원소는 뒤에 놓이도록 위치를 바꾼다. 그 결과 부분 정렬이 완성되고, 왼쪽과 오른쪽 부분을 이와 비슷한 방식으로 재귀적으로 정렬해 나가는 것.

1. 최선의 경우 : 만약 모든 원소가 동일하다면, 평균적으로 단순히 배열을 한 차례 순회하고 끝날 것이다. O(N)
2. 최악의 경우 : 배열에서 가장 큰 값이 계속해서 축이 되는 경우. 재귀 호출이 배열을 절반 크기로 나누지 못하고, 하나 줄어든 크기의 부분 배열로 나뉘어짐. 수행 시간 O(N^2)
3. 평균적인 경우 : 위와 같은 경우는 흔한 경우가 아니므로, 수행 시간은 평균적으로 O(NlogN)이라고 할 수 있다.

보통, 대부분의 알고리즘은 최악의 경우, 그리고 평균적인 경우가 많다. 

 

공간 복잡도

시간 복잡도와 평행을 달리는 개념이며, 실제 사용되는 메모리 공간을 말한다.

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

위의 경우, O(n)시간과 O(n)공간을 사용한다. 호출될 때마다, 스택의 깊이가 깊어져, sum(4)->sum(3)->...->sum(0)의 호출이 일어난다.

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

위의 경우, pairSum함수를 마찬가지로, O(n)번 호출하였지만, 이 함수들이 호출 스택이 동시에 존재하지는 않으므로 O(1) 공간만 사용하는 것을 볼 수 있다.

 

여러 부분으로 이루어진 알고리즘 : 덧셈 vs 곱셈

알고리즘이 두 단계일 때, 어떨 때는 더하고 어떨 때는 곱해야 할까?

• 만약 알고리즘이 "A일을 모두 끝마친 후에 B 일을 수행하라"의 형태라면 O(A+B)
• 만약 알고리즘이 "A일을 할 때마다 B일을 수행하라"의 형태라면 O(A*B)

상환 시간 

ArrayList는 배열의 역할을 함과 동시에 크기가 자유롭게 조절되는 자료구조이다. 원소 삽입 시 필요에 따라 배열의 크기를 증가시킬 수 있기 때문에 공간이 바닥날 일은 없다. 

ArrayList는 배열로 구현이 되어 있는데, 배열의 용량이 꽉 찼을 때, ArrayList 클래스는 기존보다 크기가 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사한다. 이때의 삽입 연산의 수행 시간은 어떻게 될까? 

배열이 가득 차 있는 경우의 삽입 연산 

배열이 가득 차 있는 경우를 생각해보면, 배열에 N개의 원소가 들어 있을 때 새로운 원소를 삽입하려면 O(N)이 걸린다. 크기가 2N인 배열을 새로 만들고, 기존의 모든 원소를 새 배열로 복사해야 하기 때문이다! 

하지만, 보통 가득 차있는 경우는 드물고, 대다수의 경우 배열에 가용 공간이 존재하고 이때 삽입 연산은 O(1)이 걸린다!

 

두 가지 경우를 포함한 전체 수행 시간을 구하기 위해서, 상환 시간이라는 개념을 이용하면 쉽게 구할 수 있다. 최악의 경우는 가끔 발생하지만, 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용(수행 시간)을 분할 상환한다는 개념이다. 

 

위의 경우, 배열의 크기가 2의 제곱수가 되었을 때 원소를 삽입하면 용량이 두 배로 증가한다. 배열의 크기가 1, 2, 4, 8, 16 , ... , X일 때 새로운 원소를 삽입하면 배열의 용량이 두 배로 증가하고, 이 때 기존의 1, 2, 4, 8, 16 , ... , X개의 원소 또한 새로운 배열로 복사해주어야 한다. 이 원소들은 1부터 X가 될 때까지, 혹은 X부터 1이 될때까지 두 배씩 증가/감소하는 수열이다. 이때, X+X/2+X/4+X/8+...+1의 합은 대략 2X와 같다. (이 식이 정확하게 이해가 안감)

 

따라서, X개의 원소를 삽입했을 때 필요한 시간은 O(2X)이고, 이를 분할 상환해보면, 삽입 한 번에 필요한 시간은 O(1)이다. 상수 시간이 소요되다가, 배열의 원소가 2의 제곱수가 되었을 때만 O(2X) 비용이 소요된다. 

 

logN 수행 시간 

이진 탐색을 생각해보자. 이진 탐색은 N개의 정렬된 원소가 들어 있는 배열에서, 원소 x를 찾을 때 사용된다. 먼저 원소 x와 배열의 중간값들을 비교한다. x==중간값을 만족하면 이를 반환한다. 총 수행 시간은 N을 절반씩 나누는 과정에서 몇단계 만에 1이 되는지에 따라 추정된다. 

N=16
N=8
N=4
N=2
N=1

2^k=N을 만족하는 k가 무엇인지를 구하기 위해, log를 사용한다. 이처럼, 어떤 문제에서 원소의 개수가 절반씩 줄어든다면, 그 문제의 수행 시간은 O(logN)이 되 가능성이 크다. 여기서, 로그의 밑이 2인데, big-O에서는 로그의 밑을 고려할 필요가 없으므로 무시하면 된다. 

 

재귀적으로 수행 시간 구하기 

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

이 경우, 함수가 두 개이므로 성급하게 O(n^2)라고 생각할 수 있다. 하지만, 답은 틀렸다.

수행 시간을 추측하지 말고 코드를 하나씩 읽어 나가면서 수행 시간을 계산해보면, f(4)를 구할 때, f(3)은 f(2)를 거쳐서 결국 f(1)까지 도착한다. 

트리의 깊이가 N이고, 각 노드(함수 호출)는 두 개의 자식 노드를 가지고 있다. 따라서, 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출하게 된다. 

1. root (level=0)일 때, 노드 1개, (2^0)
2. level=1일 때, 노드는 2개, (2^1)
3. level=2일 때, 노드는 4개, (2^2)
4. level=3이 때, 노드는 8개, (2^3)

이므로, 전체 노드의 개수는 이를 다 더한 2^0+2^1+...+2^n = 2^(n+1)-1의 식으로 표현된다. 수행시간은 O(2^n)이 될 것이다. 다수의 호출로 이루어진 재귀 함수에서 수행 시간은 보통 O(분기^높이)로 표현되곤 한다. 로그와는 달리, 지수에서는 밑을 무시할 수 없다. 2^2n과 2^n은 매우 다르다.

 

예제 및 연습 문제

/*예제3*/

void printUnorderedPairs(int[] array){
	for(int i=0;i<array.length;i++){
		for(int j=i+1;j<array.length;j++){
			System.out.println(array[i]+","+array[j]);
		}
	}
    }

(1) 내가 한 방법 : 반복 횟수 세어보기

처음에 j는 n-1번 반복하다가, 점점 줄어들어 1이 된다. 따라서, (n-1)+(n-2)+...+1=(n-1)(n-2)/2가 되므로 O(n^2)이다.

(2) 코드가 무엇인지 파악하기

코드 자체가 무엇을 의미하는지를 생각한다. 이 함수는 j가 i보다 큰 모든 (i,j)쌍을 반복하여 출력한다. n=8이라 가정하면,

다음과 같이 출력된다. 이는 n*n의 절반 크기인 n^2/2크기의 행렬처럼 보인다. 따라서, O(n^2)시간이 걸린다.

(3) 평균을 이용한 방법

바깥의 루트는 n번 반복한다. 안쪽 루프는 얼마나 많은 일을 하고 있을까? 바깥 루프에 의존적이지만, 평균을 구해볼 수 있을 것이다. 1,2,3,4,...,n의 수열에서, 평균값은 대략 n/2가 된다. 따라서, 안쪽루프의 평균 반복횟수는 n/2이고, 이 루프는 총 n번 수행되므로 전체 수행횟수는 n^2/2, 즉 O(n^2)가 된다. 

 

/* 예제 8 */

여러 개의 문자열로 구성된 배열이 주어졌을 때, 
각각의 문자열을 먼저 정렬하고 그 다음에 전체 문자열을 사전순으로 다시 정렬하는 알고리즘.

<틀린 분석>

각 문자열을 정리하는데 O(NlogN)이 소요되기 때문에, 모든 문자열을 정렬하는 데 O(N*NlogN)이 소요될 것이다. 그 후, 사전순으로 정렬하면 O(N^2logN+NlogN)-> O(N^2logN)이 될 것이다.

왜 틀렸을까? N을 서로 다른 두 가지 경우에 혼용하여 사용했기 때문이다. 

<정답>

가장 길이가 긴 문자열의 길이를 s라 하고, 배열의 길이를 a라 한다.

• 각 문자열을 정렬하는 데 O(slogs)가 소요된다.
• a개의 문자열 모두를 정렬해야 하므로, 총 O(a*slogs)가 소요된다.
• 문자열 두 개를 비교하는 데 O(s)시간이 소요되고, 총 O(aloga)번을 비교해야 하므로, 사전순으로 정렬할 때, O(a*sloga)가 소요된다. 
• 위의 두 부분을 더해주면, 전체 시간 복잡도는 O(a*s(loga+logs))가 된다. 

/* 예제 9 균형 이진 탐색 트리 */

int sum(Node node) {
	if (node==null) {
		return 0;
	}
	return sum(node.left) + node.value + sum(node.right);
}

(1) 코드의 의미 파악하기

트리의 각 노드를 한 번씩 방문한 뒤에, 각 노드에서 상수 시간에 해당하는 일을 수행한다. 따라서, 수행 시간은 노드의 개수와 선형 관계에 있다. n개의 노드가 있다고 가정할때, 수행 시간은 O(n)이 된다.

(2) 재귀호출 패턴분석

함수에 나온 트리는 균형 이진 탐색 트리이다. 총 n개의 노드가 있다면 깊이는 대략 log n이 된다. 재귀 함수에 분기가 여러 개 존재할 경우, 수행 시간은 일반적으로 O(분기^깊이)가 되므로 이 수식에 따르면 수행시간은 O(2^logN)이 된다. 

log의 정의에 따라, 2^logn은 n이 되고 수행시간은 O(n)이 된다. 

 

/* 예제 10 */

boolean isPrime(int n){
	for(int x=2;x*x<=n;x++)
		if(n%x==0){
        	return false;
        }
   }
   return true;
}

소수인지 아닌지 판별하는 문제. 최악의 경우 x=2~sqrt(n)까지만 함수가 돌아가므로 시간복잡도는 O(root(n))이다.

 

void permutation(String str){
	permutation(str, "");
}

void permutation(String str, String prefix){
	if(str.length()==0){
		System.out.println(prefix);
    } else {
    	for (int i=0;i<str.length();i++){
        	String rem=str.substring(0,i)+str.substring(i+1);
            permutation(rem,prefix+str.charAt(i));
        }
    }
}