복잡도 분석하기 - 시간복잡도와 공간복잡도

hyeon930·2020년 1월 26일
0

코딩인터뷰 완전분석

시간복잡도

  • 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(분기 ^ 깊이)의 패턴을 갖는다.
profile
사용자와 가장 가까운 개발자가 되고 싶습니다.

0개의 댓글