시간 복잡도(big-O)

코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조

• 실행 시간을 나타내기 위해 사용되는 개념이 시간 복잡도이다.

• 변수 N을 통해 O(logN), O(NlogN),… 등과 같이 표현하기도 하지만 이외에도 다양한 변수가 포함될 수 있다.

  • 예를 들어, 너비가 w이고 높이가 h인 울타리를 칠한다고 할 때 소요 시간은 O(wh)로 표현할 수 있고 p번 덧칠한다면 O(pwh)로 표현할 수 있다.

• 상수항과 지배적이지 않은 항은 무시하자.

  • big-O는 단순히 증가하는 비율을 나타내는 개념으로 수행 시간에 지배적이지 않은 항은 무시할 수 있다.

  • 두 개의 중첩되지 않은 루프로 이루어진 코드의 수행 시간을 O(2N) 과 같이 표현할 수도 있지만 이는 결국 O(N)과 같은 의미이다.

  • 마찬가지로, O(N^2 + N)과 같은 수행 시간이 있을 때, N^2이 지배적인 항이므로(N에 비해 빠르게 증가하기 떄문) O(N^2 + N) 은 O(N^2) 이 된다.

  • 즉, big-O 는 수행 시간이 어떻게 변화하는지를 표현해주는 도구이다.

• 덧셈? 곱셈??

  • 두 단계로 이루어진 알고리즘이 있을 경우, 수행 시간을 어떤 경우에는 더하고 혹은 곱해야 하는걸까?

    1 2 3 4 5 6 7

    ### 덧셈 수행 시간 : O(A+B) for (int a : arrA) { print(a); } for (int b : arrB) { print(b); }

  • 위와 같이 A의 일을 모두 끝마친 후 B의 일을 시행하는 형태라면 A와 B의 수행 시간을 더해야 한다.

    1 2 3 4 5 6

    ### 곱셈 수행 시간 : O(A*B) for (int a : arrA) { for (int b : arrB) { print(a + "," + b); } }

  • 위와 같이 A의 일을 할 때마다 B의 일을 시행하는 형태라면 A와 B의 수행 시간을 곱해야 한다.

• log N 수행 시간

  • logN 수행 시간이 어떻게 나오는지 알기 위해 이진 탐색을 생각해보자. 이진 탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때, 배열의 중간값과 x의 값을 비교하여 배열의 부분을 재탐색하는 것이다.

  • 예를 들어, 16개의 원소를 가진 배열을 생각해보자. N = 16

  • 이진 탐색을 통해 각 단계별로 탐색해야 하는 원소의 개수는 다음과 같다.

    1 2 3 4 5

    N = 16 # 처음 N = 8 # 나누기 2 N = 4 # 나누기 2 N = 2 # 나누기 2 N = 1 # 나누기 2, 찾고자하는 원소 x를 찾았다.

  • 즉, 총 수행 시간은 N을 절반씩 나누는 과정을 몇단계 거쳐서 1이 되는지에 따라서 결정된다.

  • 위의 경우를 반대로 생각해보자. 1에서 16으로 증가하려면 1에서 2를 몇번 곱해야 할까?

    1 2 3 4 5

    N = 1 # 처음 N = 2 # 곱하기 2 N = 4 # 곱하기 2 N = 8 # 곱하기 2 N = 16 # 곱하기 2

  • 다시 말해, 절반씩 나누는 과정(나누기2)을 1에서 2를 곱해가는 과정으로도 표현할 수 있다는 뜻이다.

  • 이는, 2를 k번 곱해서 N이 된다고 말할 수 있으며 다음과 같은 수식으로 나타낼 수 있다.

    1

    2^k = N

  • 위 수식을 만족하는 k는 무엇인가? k를 찾기 위해 양 변에 밑이 2인 로그를 취해주자.

    1 2 3 4

    ### <밑이 2인 로그입니다.> ---> log(2^k) = logN ---> k * log2 = logN ---> k = logN (∵ log2 = 1)

  • big-O 에서는 로그의 밑을 고려할 필요가 없다. 위에서 밑이 10인 로그를 취했다 할지라도 이는 상수항일 뿐이다. 시작할 때 말했듯이 big-O 에서 상수항은 무시할 수 있다.

• 재귀함수의 수행 시간

  • 다음과 같은 재귀함수의 수행 시간은 어떻게 될까?

    1 2 3 4 5 6

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

  • 함수 f가 두번 호출되는것을 보고 O(N^2)이라고 생각할 수 있지만 틀렸다.

  • f(4) 일때 위와 같이 f(3)을 두번 호출하고 f(3)은 f(2)를 거쳐 f(1)까지 호출한다.

  • 위와 같이 두 개의 자식 노트를 가진 경우 총 호출 횟수는 얼마인가? 호출 횟수를 표로 나타내보자.

• • 따라서, 전체 노드의 개수는 2⁰ + 2¹ + 2² + 2³ + … + 2^N = 2^N+1 - 1 이다.

  • 즉, 위와 같은 재귀 함수의 수행 시간은 O(2^N)이 된다.

  • 보통 다수의 호출로 이루어진 재귀 함수의 수행 시간은 O(분기^깊이) 로 표현할 수 있다. 여기서 분기란 재귀 함수가 자신을 재호출 하는 횟수를 뜻한다.