코딩인터뷰 완전분석
시간복잡도
- Big-O, Big-Omega, Big-theta
- Big-O는 상한, 실제로 Big-O보다 작으면 된다.
- Big-Omega는 등가 혹은 하한, 실제로 Big-Omega 보다 빠를 수 없다(커야한다).
- Big-theta는 O와 Omega 둘 다를 의미한다. 즉, O(N) 이면서 Omega(N)일 때 theta(N)이다.
- 가장 흔하게 사용되는 것
- O(log N), O(NlogN), O(N), O(N^2), O(2^N)
공간복잡도
공간 복잡도는 시간 복잡도와 평행선을 달리는 개념이다. 크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다.
-
n번 호출한다고 O(n)의 공간복잡도를 가진다고 할 수 없다.
int sum(int n){ if (n <= 0){ return 0; } return n + sum(n - 1); } // 호출될 때마다 스택의 깊이가 깊어진다. 따라서 n번 호출하고 O(n)의 공간복잡도를 가진다. sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0)int pairSumSequence(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)이다.
Big-O
-
상수항은 무시한다.
- 그러나 O(N)이 언제나 O(2N)보다 나은 것은 아니다.
-
지배적이지 않은 항은 무시한다.
- O(N^2 + N)은 O(N^2)이 된다.
- O(N + logN)은 O(N)이 된다.
- O(5*2^N + 1000N^100)은 O(2^N)이 된다.
-
수행 시간의 덧셈과 곱셈
- 만약 알고리즘이 "A 일을 모두 끝마친 후에 B 일을 수행하라"의 형태라면 A와 B의 수행 시간을 더해야 한다.
- 만약 알고리즘이 "A 일을 할 때마다 B 일을 수행하라"의 형태라면 A와 B의 수행 시간을 곱해야 한다.
-
상환시간
-
ArrayList에서 삽입연산을 수행하는 경우 공간이 남아 있을 때는 O(1)이지만 배열이 가득차 있는 경우에는 기존 배열의 크기에 2배의 배열을 선언하여 기존 배열을 복사하기 때문에 O(N)이다.
-
두 가지 경우를 모두 포함하는 전체 수행 시간을 따지기 위해서는 상환시간이라는 개념을 도입한다.
-
최악의 경우는 가끔 발생하지만 한 번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용(수행 시간)을 분할 상환 한다는 개념이다.
배열의 크기가 2의 승수가 되었을 때 원소를 삽입하면 용량이 두 배로 증가한다. 즉, 기존 배열의 크기가 1, 2, 4, 8, 16, ..., X 이 되었을 때 삽입 연산을 수행하면 배열의 크기가 두 배로 증가하고 이때 기존의 1, 2, 4, 8, 16, ..., X개의 원소 또한 새로운 배열로 복사된다. 합을 구하면 1 + 2 + 4 + 8 + 16 + ... + X는 X + X/2 + X/4 + X/8 + X/16 + ... + 1과 같고 그 합은 대략 2X와 같다. 따라서 X개의 원소를 삽입했을 때 필요한 시간은 O(2X)이고, 이를 분할 상환해보면 삽입 한 번에 필요한 시간은 O(1)이다.
-
-
log N 수행 시간
-
이진 탐색을 생각했을 때 총 수행 시간은 N을 절반씩 나누는 과정에서 몇 단계 만에 1이 되는지에 따라 결정된다. 그 때 감소하는 순서를 뒤집어서 증가하는 순서로 생각해본다면, 숫자 1에 2를 몇 번 곱해야 N이 될까?
2^k = N을 만족하는 k는 무엇인가? 이 때 사용되는 것이 바로 로그다. -
어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(log N)이 될 가능성이 크다.
-
Big-O에서는 로그의 밑을 고려할 필요가 없다.
-
-
재귀적으로 수행 시간 구하기
- 일반적으로 O(분기 ^ 깊이)의 패턴을 갖는다.
그냥 개발자