5일차
게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.59 ~ p. 70
내용 정리
6. big-O
big-O 시간은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.
비유하기
파일을 보낼 때 크기가 작다면 전송하는게 빠르지만 굉장히 크다면 물리적으로 직접 가는게 빠를것.(1테라를 미국에 메일로 보내느니 들고 비행기타고 가는게 낫다!)
시간 복잡도
점근적 실행 시간(asymptotic runtime), 또는 big-O 시간에 대한 개념에 대해 얘기해보자.
데이터 전송 ‘알고리즘’의 실행 시간에서
- 온라인 전송: O(s), s가 파일의 크기이다. 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가
- 비행기 전송: O(1), 파일 크기랑 상관없다. 크든 작든 비행기 한대 가는 시간이니까!
O(s)가 커지다 보면 어느 순간 O(1)보다 커지게 된다. O(1)이 얼마든, O(s)가 얼마나 천천히 커지든 언젠가는 무조건!
big-O, big-Θ, big-Ω
- big-O : 시간의 상한, 알고리즘의 수행시간은 big-O보다 작거나 같음을 의미한다.
- big-Ω : 등가 혹은 하한, 알고리즘의 수행시간은 big-Ω보다 빠를 수 없다.
- big-Θ : O, Ω 둘 다 의미한다. 어떤 알고리즘의 수행시간이 O(N) 이자 Ω(N)이면 Θ(N)로 표현할 수 있다.
즉 각각 상한, 하한, 딱 맞는 수행시간을 의미한다.
학계에선 위와 같지만, 보통 실무에서는 Θ와 O를 하나로 합쳐 표기하며 그냥 O로 표기하는 경우도 많다. O가 딱 맞는 알고리즘 표기인것처럼..
최선의 경우, 최악의 경우, 평균적인 경우
알고리즘의 수행 시간을 세 가지 다른 방법으로 나타낼 수 있다. 퀵 정렬(Quick sort)의 경우를 보자.
퀵 정렬은 ‘축’이 되는 원소 하나를 무작위로 뽑은 뒤 이보다 작은 원소들은 앞에, 큰 원소들은 뒤에 놓이도록 원소의 위치를 바꾼다. 그 결과 ‘부분 정렬’(partial sort)이 완성되고, 그 뒤 왼쪽과 오른쪽 부분을 이와 비슷한 방식으로 재귀적으로 정렬해 나간다.
- 최선의 경우 : 모든 원소가 동일하다면 평균적으로 단순히 배열을 한 차례 순회하고 끝난다. 따라서 수행 시간은 O(N)
- 최악의 경우 : 매번 가장 큰 원소가 축이 된다면? 나누어지는 부분 배열이 딱 하나 작은 크기가 된다. 결국 수행 시간은 O(N^2)
- 평균적인 경우 : O(NlogN)
보통은 평균적인 경우와 최악의 경우가 같다.
공간 복잡도
알고리즘에선 시간뿐 아니라 메모리(공간)도 신경써야 한다.
크기가 n인 배열을 만들고자 한다면 O(n)이, nxn 크기의 2차원 배열이면 O(n^2)이 필요하다. 또한 재귀 호출을 위한 스택 공간도 여기에 포함된다.
1
2
3
4
5
6
int sum(int n) {
if ( n <= 0) {
return 0;
}
return n + sum(n-1);
}
위 코드는 호출될 때 마다 스택의 깊이는 깊어진다.
sum(4) -> sum(3) -> sum(2) -> sum(1)
이런 경우 호출 횟수가 n 이라면 O(n)의 공간을 사용한다.
하지만 n 번 호출되었다고 항상 O(n)이 사용되진 않는다.
1
2
3
4
5
6
7
8
9
10
11
int pairSumSequence(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += pairSum(o, i + 1);
}
return sum;
}
int pairSum(int a, int b){
return a + b;
}
여기서 pairSum 함수를 O(n)번 호출했지만 호틀 스택에 동시에 존재하지 않으므로 O(1)의 공간만 사용한다.
상수항은 무시하라
O(2N)으로 표기하지 않고 O(N)으로 표기한다.
지배적이지 않은 항은 무시하라
O(n^2 + n)이라면 n은 무시하라. 둘 중 큰 것만 신경써라.
하지만 O(B^2 + A)는 B와 A의 관계를 모른다면 함부로 A를 지워선 안된다.
big-O 시간의 증가율 : O(X!) > O(2^x) > O(X^2) > O(XlogX) > O(X) > O(logX)
여러 부분으로 이루어진 알고리즘 : 덧셈 VS 곱셈
-
알고리즘이 A 일을 모두 끝마진 후에 B 일을 수행하면 두 수행시간을 더한다.
-
A 일을 할 때 마다 B 일을 수행하면 두 수행시간을 곱한다.
상환 시간
ArrayList(동적 가변크기 배열)는 배열의 역할을 함과 동시에 크기가 자유롭게 조절되는 자료구조이다. 이 배열의 용량이 꽉 찼을 때, ArrayList 클래스는 기존보다 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사한다.
그렇다면 여기에 삽입 연산을 할 때 수행 시간은 어떨까?
- 배열이 가득 차 있다면 O(N)이 걸린다. 크기가 2N인 배열을 새로 만들고 복사 해주어야야 하기 때문이다.
- 하지만 대부분의 경우 가용 공간이 존재하므로 O(1)이 걸린다.
상환 시간은 배열이 가득 차 있는 최악의 경우는 가끔 발생하지만 한번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용(수행 시간)을 분할 상환한다는 개념이다.
여기선 배열의 크기가 2의 거듭제곱 형태일 때 두배로 늘어난다. 즉 1,2,4,8,16,32,… 일 때이다. 합은 등비수열의 합 공식을 이용해보면 대략 2X와 비슷하다! 이를 X로 나누면 결국 O(1)임을 알 수 있다.
좀더 쉽게 설명해보자면,
크기가 n인 배열에서 n일 때를 제외하고는 모두 가용공간이 있으니 배열에 추가하는 수행시간은 O(1)이다. 크기가 n일 때만 O(n)이 걸린다. O(1)이 n-1번이므로 O(n)이라 할 수있고 O(n)이 1번이므로 마찬가지로 O(n)이다. 이 둘을 합치면 O(2n). 총 n번일 때의 합이므로 1번 당 수행시간은 O(2)인데, 상수는 무시하기로 했으므로 O(1)임을 알 수 있따.
log N 수행시간
수행시간에서 log가 왜 자주 나타날까? 이진 탐색(binary search)를 살펴보자. N개의 정렬된 원소 배열에서 x를 찾는 과정이다. 배열의 중간값과 x를 비교하여 x가 크면 배열의 가운데에서 오른쪽 부분을, 작을 떄는 왼쪽 부분을 탐색한다. 이 후 새로운 중간값을 설정한다. 이 과정을 반복하다가 중간값과 x가 같아질 때 반환하는 것이다.
각 과정에서 처음에는 배열의 크기가 N이고 이후 반으로 줄어들게 되니 N/2, N/4, … , 1이 된다. 이 수열을 거꾸로 생각해보면 1 에서 N이 될때까지 2를 곱하는 것이다. 몇번 곱해야할까? 이 과정에서 log가 나타나는 것이다. 2를 log_2(N)번 제곱하면 N이 나오기 때문이다.
나는 면접에서 이와 관련된 질문을 듣다가 log의 밑이 10인것과 2인것이 차이가 있느냐는 질문을 들었는데 대답을 못했다.. 로그의 밑은 상수항으로 췰급되기 때문에 big-O 표기법에서 무시해도 괜찮다. 하지만 지수에서는 안된다. 8^n = 2^n * 2^2n 이다. 지수의 밑이 2에서 8이 되었지만 둘은 2^2n 만큼의 차이가 있다. 꼭 알아두자!
재귀적으로 수행 시간 구하기
1
2
3
4
5
6
int f(int n) {
if (n<=1) {
return 1;
}
return f(n-1) + f(n-1);
}
함수 f가 2번 호출되었으니 O(N^2)일까? 아니다
f(4)는 f(3)을 2번 호출한다.
f(3)은 f(2)를 2번 호출한다.
f(2)는 f(1)을 2번 호출한다.
이를 통해 다시 올라가보면 f(4)는 f(3)을 2번 호출하는데 이는 f(2)를 4번 호출하는 것과 같고 f(1)을 8번 호출하는 것과 같다. 즉 2배씩 증가하므로 총 호출 횟수는 2가 공비인 등비수열의 합이라 2^N의 형태이다. O(N^2) 보다 훨씬 큰 수행시간임을 알 수 있다.
예제 및 연습 문제
예제 1
1
2
3
4
5
6
7
8
9
10
11
void foo(int[] array) {
int sum = 0;
int product = 1;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
for (int i = 0; i < array.length; i++) {
product *= array[i];
}
System.out.printLn(sum = ", " + product);
}
for 반복문이 2개 있지만 각자 별개로 발생한다. 두 수행시간은 덧셈이고, 상수는 무시한다.
답 : O(N)
예제 2
1
2
3
4
5
6
7
void printPairs(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
System.out.println(array[i] + "," + array[j]);
}
}
}
첫번째 for문이 반복될 때마다 두번째 for문이 모두 순회한다. 둘은 곱해진다.
답 : O(N^2)
예제 3
1
2
3
4
5
6
7
void printUnorderPairs(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]);
}
}
}
첫번째 for문이 n번 반복된다고 하자. 두번째 for문은? i보다 1 큰 수를 의미하므로 이 반복횟수는 점차 1씩 줄어들게 된다. i가 반복될 때마다 1씩 커지기 때문이다.
i = 0,1,2,…,N-1 이기 때문에 j의 반복횟수는 N-1,N-2,…,1 이 된다. 따라서 총 수행 횟수는 1부터 N-1까지의 합을 의미한다. 공식에 따라 (N-1)N/2 이므로
답 : O(N^2)
예제 4
1
2
3
4
5
6
7
8
9
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i =0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
if (arrayA[i] < arrayB[j]) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
O(N^2)이 아니다. 두 반복문은 arrayA와 arrayB라는 다른 배열의 길이만큼 반복된다. 따라서 각각의 길이를 N,M이라 하면
답 : O(NM)
예제 5
1
2
3
4
5
6
7
8
9
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i<arrayA.length; i++) {
for (int j = 0; i<arrayB.length; j++) {
for (int k = 0; k< 100000; k++) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
100000이 꽤 크다고 쫄지말자. 그냥 상수다. 배열 A와 B의 길이를 N, M이라 한다면
답 : O(NM)
예제 6
1
2
3
4
5
6
7
8
void reverse(int[] array){
for (int i = 0; i < array.length/2; i++) {
int other = array.length -i -1;
int temp = array[i];
array[i] = array[other];
array[other] = temp;
}
}
배열 길이 N의 절반인 n/2만큼 반복한다. 2분의 1도 당연히 상수기 때문에
답 : O(N)bl
예제 7
다음 중 O(N)과 같은 것들은?
- O(N+P), P < N/2 일 때
답 : 같다. P가 N/2라 해도 O((3N/2)가 되어 상수는 무시되므로 O(N)과 같다.
- O(2N)
답 : 같다. 상수는 무시한다.
- O(N+logN)
답 : 같다. logN은 N에 비해 굉장히 작은 증가율을 보여 무시할 수 있다. 지배적인 항인 N만 본다.
- O(N + M)
답 : 다르다. M과 N의 관계에 대해 알 수 없기 때문에 M을 함부로 무시할 수 없다.
예제 8
여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그 다음에 전체 문자열을 사전순으로 다시 정렬하는 알고리즘이 있다고 가정하자. 이 알고리즘의 수행 시간은 어떻게 되곘는가?
답 : O( AS(log A + log S))
책에선 각각의 구성 문자열 중 가장 길이가 긴 문자열의 길이를 S라 하였다. 다른 문자열들은 길이가 모두 이보다 짧으므로 O(SlogS)로 나타낼 수 있다. (big-O는 상한선을 의미하니까) 배열의 길이(다시 말해 문자열의 갯수)가 A라 하였으므로 문자열을 모두 정렬하면 A _ SlogS 이다. 이제 배열을 사전순으로 정렬해야한다. AlogA 라고 생각하려면 숫자를 정렬해야 한다. 숫자의 비교는 O(1)이라 무시했었으니까. 하지만 길이가 S인 문자열의 비교는 O(S)이다. 즉, O(S _ AlogA) 인 것이다. 이 둘을 더하면 ASlog(S) + AS(logA) = O(AS(log A + log S)) 이다. S와 A의 관게는 나타나지 않았으므로 더 무시하거나 삭제할 것은 없다.
예제 9
다음 균형 이진 탐색 트리에서 모든 노드의 값을 더하는 코드의 수행시간은?
1
2
3
4
5
6
int sum(Node node) {
if (node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
답 : k 가 높이일 때 O(2^k), 노드 갯수가 n일 때 O(n)
함수 sum은 각각 왼쪽 자식과 오른쪽 자식을 parameter로 하여 sum을 호출한 후 자신 node 값을 더한 값을 반환한다. 다시 말해, 이 함수는 자신의 자식 수 만큼 함수를 추가로 호출한다. 균형 이진 탐색 트리이므로 모든 노드는 자식이 있다면 2개 있고, 없다면 아예 없다.
트리의 높이를 생각해 보았을 때, 한층 내려가면서 2개씩 호출한다. 높이가 k이라면? 층이 k+1개라는 의미를 뜻하고, 리프노드가 2^k개 호출된다.
노드의 갯수로 생각해보자. 노드가 n개 있다고 가정해보자. 깊이가 k라는 것은 어떤 의미일까? 각 층에는 2의 거듭제곱만큼 노드가 존재한다. 1층에는 1개이므로 2^0, 2층에는 2^1개, … , k+1층에는 2^k 개. 노드의 갯수는 이들의 합이다. 1 + 2 + 4 + … + 2^k = 2^(k+1)-1 = n 이다. 거추장스러운 상수를 제하면 2^k = n이라고 볼 수있으니 k = log_2(n)이다. 위에 대입하면 O(n)임을 알 수 있다.
예제 10
다음은 현재의 값보다 작은 수들로 나누어 떨어지는지 확인함으로써 현재의 값이 소수인지 아닌지 판별하는 함수이다. 이때 현재의 값보다 작은 수 전체를 이용할 필요는 없고 n의 제곱근까지만 확인해 보면 된다. 만약 제곱근보다 큰 수로 나누어 떨어지는 경우가 존재한다면, 그에 상응하는 제곱근보다 작은 수로도 나누어 떨어지기 때문이다.
다음 함수의 시간복잡도는 어떻게 되겠는가?
1
2
3
4
5
6
7
8
boolean isPrime(int n) {
for (int x = 2; x *x <= n; x++) {
if (n%x == 0) {
return false;
}
}
return true;
}
답 : O(n^(1/2))
x는 2부터 1씩 증가하면서 n과 나누어 떨어지는지 확인한다. 이 횟수는 n의 제곱근보다 작을 때까지 반복된다. n^(1/2)의 정수부분까지. 딱히 생략하거나 무시할 부분은 없다.
예제 11
n의 계승(factorial) n!을 구하는 코드이다. 시간복잡도는?
1
2
3
4
5
6
7
8
9
int factiorial(int n){
if (n < 0) {
return -1;
} else if (n == 0) {
return 1;
} else {
return n * factorial(n-1);
}
}
답 : O(n)
factorial(n) -> factorial(n-1) -> … -> factorial(0), n번 호출된다.
예제 12
다음은 문자열로 나타낼 수 있는 순열(permutation)의 갯수를 구하는 코드이다. 시간복잡도는?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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));
}
}
}
답 : O(N^2 * N! )
문자열의 길이를 N이라 하자. 이 문자열로 순열을 만들 때 첫자리에 오는 후보는 N개, 두번째 자리는 N-1개, … 가 반복된다. 따라서 순열은 N!개 만들어진다.
각 순열이 만들어지려면 2번째 함수에서 else 안의 for문을 통과해야 한다. for문은 문자열의 길이 N만큼 반복된다. N!개가 모두 N번씩 실행되므로 N*N! 이 실행횟수이다.
각 순열에서 문자열이 7번행에서 print 되는데 O(N)의 시간이 걸리므로 또 곱해준다.
예제 13
N번째 피보나치 수를 구하는 코드이다.
1
2
3
4
5
int fib(int n) {
if (n <= 0) return 0;
else if ( n== 1) return 1;
return fib(n-1) + fib(n-2);
}
답 : O(2^n)
fib(n)는 2개로 나눠지며 fib(n-1)로 낮아진다. 즉 상수인 fib(1),fib(0) 까지 가려면 2^n 개가 된다.
예제 14
0부터 n까지의 피보나치 수열 전부를 출력하는 함수의 시간 복잡도는?
1
2
3
4
5
6
7
8
9
10
void allFib(int n) {
for (int i = 0; i < n; i++) {
System.out.println(i + ": " + fib(i));
}
}
int fib(int n) {
if (n <= 0) return 0;
else if (n==1) return 1;
return fib(n-1) + fib(n-2);
}
답 : O(2^n)
fib(n)이 O(2^n)임은 위 문제로 증명했다.
따라서 0부터 n까지 출력하려면
2^0 + 2^1 + 2^2 + … + 2^n 이므로 등비수열의 합이니까
예제 15
0부터 n까지 피보나치 수열 전부를 출력하는 코드다. 하지만 이번에는 이전에 계산된 결과값을 정수 배열에 저장(즉, 캐시)한다. 알고리즘 중간에 이미 저장된 값이 있다면 그 캐시값을 반환한다. 수행 시간은 어떻게 되겠는가?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void allFib(int n) {
int[] memo = new int[n+1];
for (int i = 0; i < n; i++) {
System.out.println(i + ": " + fib(i, memo));
}
}
int fib(int n, int[] memo) {
if (n<=0) return 0;
else if (n==1) return 1;
else if (memo[n] >0) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
답 :
아는 사람들은 알겠지만 다이나믹 프로그래밍의 개념이다. 따라서 배열에 저장되어 있어 아는 값 바로 다음 값은 두 개의 합을 통해 구할 수 있다. 피보나치에서 0,1의 값을 알고 있으므로 2, 3, 4, … 에 따라 각각 O(1)이다. n까지 마찬가지이므로 n을 구하는 수행 시간은 O(n)이다.
예제 16
1과 n을 포함하여 그 사이에 있는 모든 2의 승수(power of 2)를 출력하는 함수이다. 예를 들어 n이 4 일 때 이 함수는 1, 2, 4를 출력한다. 수행시간은 어떻게 되겠는가?
1
2
3
4
5
6
7
8
9
10
11
12
13
int powerOf2(int n) {
if (n<1) {
return 0;
} else if (n==1) {
System.out.println(1);
return 1;
} else {
int prev = powerOf2(n/2);
int curr = prev * 2;
System.out.println(curr);
return curr;
}
}
답 : O(log_2(n))
n을 반으로 줄인 값을 parameter로 함수를 반복해서 호출하고 있다.
n이 1이 될떄까지 이므로 log_2(n) 번일 것이다.
읽고 나서
항상 알고리즘 문제 풀 때 시간복잡도에 대해 이야기 하지만 정작 내가 내 코드가 어떤 시간복잡도를 가지는 지는 생각해본적없다. 저게 빠르다, 이건 느리다로 생각하며 시키는 대로 풀었기 떄문이다. 오늘 많이 공부해서 앞으로는 할 수 있을것 같다.
