책너두 (코딩 인터뷰 완전분석) 5일차 (~70p)

요약

• big-O
  • 시간 복잡도
    • 점근적 실행 시간을 의미
  • 최선의 경우, 최악의 경우, 평균적인 경우
    • 알고리즘에서는 최선의 경우를 고려하지 않는 경우가 많음.
  • 공간 복잡도
    • 알고리즘에서는 시간뿐 아니라 메모리 또한 신경 써야 함.
  • 상수항은 무시하라
    • 특수한 입력에 대한 시간 차이를 무시함
  • 지배적이지 않은 항은 무시하라
  • 여러 부분으로 이루어진 알고리즘 : 덧셈 vs. 곱셈
    • ex) for 문을 끊어서 하는가 중첩에서 하는가
  • 상환 시간
    • 전체 수행 시간이 일정하지 않을 때 분할 상환 개념을 이용
    • ex) ArrayList 삽입 시간
  • log N 수행 시간
    • ex) 원소의 개수가 절반씩 줄어든다.
  • 재귀적으로 수행 시간 구하기
    • O(분기^깊이)

메모

6. big-O

• big-O : 알고리즘의 효율성을 나타내는 지표 혹은 언어

시간 복잡도

• 점근적 실행 시간(asymptotic runtime), 혹은 big-O 시간에 대한 개념임.
  • ex) 온라인 전송 : O(s)
    • 여기서 s는 파일의 크기가 됨.
    • 파일의 크기가 증가함에 따라 전송 시간 또한 선형적으로 증가함
  • ex) 비행기를 통한 전송 : O(1)
    • 파일 크기에 관계 없이 전송 시간은 상수 시간 만큼 소요됨.

big-O, big-Θ, big-Ω

• O(big-O)
  • 학계에서 big-O는 시간의 상한을 나타냄
  • 즉, 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 됨.
• O(big-Ω)
  • 학계에서 등가 개념 혹은 하한을 나타냄
  • Ω 수행 시간보다 빠를 수 없음.
• O(big-theta)
  • 학계에서 O와 Ω 둘다 의미함.

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

• ex) 퀵정렬 (p 62 ~ 63 참고)
• 최선의 경우에 시간 복잡도는 별로 쓸만한 개념이 아님
  • 많은 알고리즘은 최악의 경우와 평균적인 경우가 같다.

공간 복잡도

• 알고리즘에서는 시간뿐 아니라 메모리 또한 신경 써야 함.
• 크기가 n인 배열을 만들고자 한다면 O(n) 공간이 필요함.
  • n x n 크기의 2차원 배열을 만들고자 한다면 O(n^2) 공간이 필요함.
• 재귀 호출에 사용하는 스택 공간 또한 공간 복잡도 계산에 포함됨.
  • p 64 참고

상수항은 무시하라

• 특수한 입력에 한해서 O(N)코드가 O(1) 코드보다 빠르게 동작할 수 있음.
  • 따라서 수행 시간에서 상수항을 무시해버림.
  • ex) O(2N) 은 실제로 O(N)으로 표기함.
  • p 65 참고

지배적이지 않은 항은 무시하라

• O(N^2 + N) 에서 N은 상수항은 아니지만 특별히 중요한 항도 아님.
  • 따라서 O(N^2)이 됨.
  • 이처럼 수식에서 지배적이지 않은 항은 무시해도 됨.
    • ex) O(N + logN) → O(N)
    • ex) O(5 + 2^N + 1000N^100) → O(2^N)
• 수식에 합이 남아 있을 수 있음.
  • ex) O(B^2 + A) → 하나의 항으로 줄일 수 있음. (A와 B 사이에 존재하는 특별한 관계를 알고 있지 않는 이상은..)
• p 66 big-O 시간 증가율 참고

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

• 만약 알고리즘이 “A 일을 모두 끝마친 후에 B 일을 수행하라” 의 형태라면 A와 B의 수행 시간을 더해야 함. O(A+B)
• 만약 알고리즘이 “A 일을 할 때마다 B 일을 수행하라”의 형태라면 A와 B의 수행 시간을 곱해야 함. O(A*B)

상환 시간

• ArrayList 는 배열로 구현되어 있음.
  • 배열의 용량이 꽉 찼을 때, ArrayList 클래스는 기존보다 크기가 두 배 더 큰 배열을 만든 뒤, 이전 배열의 모든 원소를 새 배열로 복사함.
  • 배열에 N개의 원소가 들어 있을 때 새로운 원소를 삽입하면 O(N)이 걸림.
    • 2N인 배열을 새로 만들고 기존의 모든 원소를 새 배열로 복사해야 하기 때문
  • 하지만, 배열이 가득 차 있는 경우는 극히 드뭄
    • 대다수의 경우 배열에 가용 공간이 존재하고, 이때 삽입 연산은 O(1)이 걸림.
• 위의 두 경우에 대한 전체 수행 시간을 따져봐야 함.
  • 상환 시간 개념을 이용하면 쉽게 구할 수 있음.
    • 최악의 경우는 가끔 발생하지만 한번 발생하면 그 후로 꽤 오랫동안 나타나지 않으므로 비용을 분할 상환 한다는 개념임.
  • ex) 1, 2, 4, 8, 16, … , X일 때 새로운 원소를 삽입하면 배열의 용량이 두 배로 증가함.
  • → X + X/2 + X/4 + X/8 + … + 1 → 대략 2X와 같음.
  • 따라서, X개 원소를 삽입할 때 필요한 시간은 O(2X) 이고, 이를 분할 상환하면 삽입 한 번에 필요한 시간은 O(1) 이다.

log N 수행 시간

• 이진 탐색의 경우, 정렬된 N 개의 원소에서 원소 x를 찾을 때 사용됨.
• 처음에는 원소 N개가 들어있는 배열에서 시작하고, 한 단계가 지나면 탐색해야 할 원소가 N/2 개로 줄어 듬.
• 총 수행 시간은 N을 절반씩 나누는 과정에서 몇 단계 만에 1이 되는지에 따라 결정됨.
  • 16에서 1로 감소하는 순서를 생각해보면, 1에서 16으로 몇번 2를 곱해야 N이 되는가?
  • 즉 2^k = N을 만족하는 k가 무엇인가? 이때 사용되는 것이 바로 로그 임.
• 어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 큼.
  • ex) 균형 이진 탐색 트리(balanced binary search tree) 에서 원소를 찾는 문제도 O(logN)임.
    • 매 단계마다 원소의 대소를 비교하여 왼쪽 혹은 오른쪽으로 내려감
    • 각 단계에서 검색해야 할 노드의 개수가 절반씩 줄어들게 되기 때문.
• big-O에선 로그의 밑을 고려할 필요가 없음.

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

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

• 함수 f 가 두 번 호출된다.
• 트리의 깊이가 N이고 각 노드(함수 호출)는 두 개의 자식 노드를 갖고 있음.
• 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출함.
  • 노드의 갯수가 깊이에 따라서 0 → 1, 1 → 2, 2 → 4, 3 → 8, 4 → 16 씩 증가함.
• 따라서 전체 노드의 갯수는 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + … + 2^N = 2^(N+1) - 1 이 됨.
  • 이 패턴은 기억해 두자.
  • 다수의 호출로 이루어진 재귀 함수에서 수행 시간은 보통 O(분기^깊이)로 표현되곤 함.
• 전체 노드 갯수는 O(2^N) 이지만 공간 복잡도는 O(N)이므로 필요한 가용 메모리의 크기는 O(N)이면 충분함.