0. 시간 복잡도 & 공간 복잡도

0. 시간 복잡도 & 공간 복잡도

시간 복잡도

기본 연산의 실행 횟수로 수행 시간을 평가

기본 연산

• 데이터 입출력
• 산술 연산
• 제어 연산

시간 복잡도

• Best Case
  • 빅 오메가 표기
  • 최선의 시나리오
• Worst Case
  • 빅 오 표기
  • 최악의 시나리오
• Average Case
  • 빅 세타 표기
  • 평균 시간

-> 알고리즘은 최악의 경우로 성능 파악. 즉 빅 오 표기인 Worst Case로 파악

빅 오 표기

O(1) - Constant

입력된 데이터 크기와 상관없이 항상 일정한 처리 시간이 걸림

    public void printNumber(int n) {
        System.out.println(n);
    }

O(log₂n) - Logarithmic

입력된 데이터 크기가 커질수록 연산 횟수가 log₂n에 비례해서 처리 시간 증가

        for (int i = 0; i < n; i *= 2) {
            ...
        }

O(n) - Linear

입력된 데이터 크기와 비례해서 처리 시간 증가

        for (int i = 0; i < n; i++) {
            ...
        }

O(nlog₂n) - Linear-Logarithmic

입력된 데이터 크기가 커질수록 처리 시간이 로그 배 만큼 증가

• Merge Sort
• Heap Sort

O(n²) - Quadratic

입력된 데이터 크기가 커질수록 처리 시간이 제곱으로 증가

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ...
            }
        }

O(2ⁿ) - Exponential

입력된 데이터 크기가 커질수록 처리 시간이 2ⁿ으로 증가

    public int printNumber(int n) {
        if (n <= 1) {
            return n;
        }

        return printNumber(n - 1) + printNumber(n - 2);
    }

공간 복잡도

알고리즘에서 사용하는 메모리의 양

    public int printNumber(int n) {
        int a = n;
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            b[i] = i;
        }

        return b[a];
    }

• a = 4byte
• b = 4byte * n

-> 4n + 4 => 데이터 크기가 증가할수록 선형적으로 증가하기 때문에 공간 복잡도는 O(n)다.