[코딩인터뷰] 1. big-O

『코딩인터뷰 완전분석』의 교재내용을 정리하였습니다. 첨부 된 코드 출처 역시 동일합니다.

big-O 시간은 알고리즘의 효율성을 나타내는 지표이다.

1) 시간 복잡도

• big-O 시간에 대한 개념
  • 파일을 누군가에 전송하고자 할 때, 온라인을 통해 전송 할 것인가? 직접 갖다줄 것인가?
  • 파일 용량이 크다면 직접 갖다주는 것이 빠르고, 파일 용량이 작다면 온라인 전송이 적합하다.
• 수행시간: 최선/ 평균/ 최악의 경우
  • 퀵 정렬의 경우 최선의 경우 ~ 최악의 경우까지 시간복잡도가 다르다.
  • cf. 퀵 정렬: 축이 되는 원소 하나를 무작위로 뽑은 뒤, 이보다 작은 원소들은 앞에, 큰 원소들은 뒤에 놓이도록 원소의 위치를 바꾼다.
  • 최선의 경우(O(N)): 배열이 이미 정렬되어 있거나, 모든 원소가 동일할 때.
  • 평균적인 경우(O(NlogN): 최선/최악의 경우는 생각보다 자주 발생하지 않는다.
  • 최악의 경우(O(N^2)): 배열에서 가장 큰 원소가 계속해서 축이 될 때, 재귀호출이 배열을 절반 크기의 부분 배열로 나누지 못함. (고작 하나 줄어든 크기의 부분 배열로 나누게 됨.)

2) 공간 복잡도

• 알고리즘에서는 공간(메모리) 또한 신경 써야 한다.
• 공간 복잡도는 시간복잡도와 평행성을 달리는 개념.
  • 크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요
  • n X n 크기의 2차원 배열을 만들고자 한다면, O(n^2)의 공간이 필요
  • 재귀호출: 재귀호출에서 사용하는 스택 공간 또한 공간 복잡도 계산에 포함 (재귀호출이 무조건 공간을 많이 차지하는 것은 아니다./ 호출 스택에 동시에 존재 할 때, 호출 될 때마다 스택의 깊이가 깊어짐 - 하기 코드 참고)

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

3) big-O 표기법

• 상수항은 무시한다. ( O(2N) → O(N) )
  • big-O는 단순히 증가하는 비율을 나타내는 개념이므로, 특수한 입력에 한해 O(N)코드가 O(1) 코드보다 빠르게 동작 할 수도 있다.
  • 이런 이유로 수행시간에서 상수항을 무시해 버린다.
• 지배적이지 않은 항은 무시한다. ( O(N^2 + N) → O(N^2) )

4) 알고리즘의 덧셈 곱셈

• 덧셈: A의 일을 모두 끝마친 후에 B의 일을 수행하는 형태라면, A와 B의 수행시간을 더한다.
• 곱셈: A 일을 할 때마다 B의 일을 수행하는 형태라면, A와 B의 수행시간을 곱한다.

5) 상환시간

• 상환시간은 이해가 부족하여, 추후 이해 후 포스팅 할 예정.

6) logN의 수행시간

• logN 의 수행시간은 어떻게 구해진 걸까?
  • 예) 이진탐색: 이진탐색은 N개의 정렬된 원소가 들어 있는 배열에서 원소 x를 찾을 때 사용 된다. 먼저, 원소 x와 배열의 중간 값을 비교한다. x가 중간값과 일치하면 이를 반환한다. x가 중간 값 보다 작으면 배열의 왼쪽 재탐색/ x가 중간 값 보다 크면 배열의 오른쪽을 재탐색한다.
  • 처음에는 원소가 N개 있는 배열에서 시작 → 한 단계가 지나면 탐색해야 할 원소의 개수가 N/2 로 줄어든다..(반복)
  • 총 수행시간은 N 을 절반씩 나누는 과정에서 몇 단계 만에 1이 되는지에 따라 결정
  • 어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN) 이 될 가능성이 크다.
  • big-O 표기법에서는 로그의 밑을 고려 할 필요가 없다.

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

• 수행시간은 추측하지 말고 코드를 하나씩 읽어 나가면서 계산해야 한다.
• 코드예시

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

• f 함수가 두 번 호출 되는 것을 보고, 수행시간을 O(N^2)으로 생각 할 수 있지만, 그렇지 않다. 시간복잡도 O(2^N) 이다.
  • 교재를 참고하면 트리모양으로 재귀적으로 수행 되는 것을 표현했다.
• 다수의 호출로 이루어진 재귀 함수에서 수행시간은 일반적으로, O(분기^깊이)로 표현된다.
  • 분기: 재귀 함수가 자신을 재호출 하는 횟수
• 상기 코드의 공간복잡도: O(N)