시간 복잡도와 공간 복잡도

itonse·2024년 5월 31일

자료구조 & 알고리즘

목록 보기

18/19

복잡도

복잡도는 알고리즘의 성능과 효율성을 나타내는 척도입니다. 주로 시간 복잡도와 공간 복잡도로 나눌 수 있으며, 각 알고리즘이 주어진 특정 크기의 입력(N)을 기준으로 수행 시간 혹은 사용 공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시합니다.

시간 복잡도: 알고리즘이 실행되는 데 걸리는 시간의 척도.
공간 복잡도: 알고리즘이 사용하는 메모리의 양(자원)의 척도.

시간 복잡도와 공간 복잡도는 반비례 하는 경향이 있는데, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단합니다.

복잡도를 나타내는 방법으로는 접근 표기법이 있으며, 주요 표기법에는 다음과 같은 것들이 있습니다:

빅오 표기법 (O): 최악의 경우를 나타냅니다.
세타 표기법 (Θ): 평균적인 경우를 나타냅니다.
오메가 표기법 (Ω): 최선의 경우를 나타냅니다.

주로 빅오 표기법과 세타 표기법이 많이 사용됩니다

시간 복잡도

알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.
수행 시간은 실행환경(OS, IDE)에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다.
-> 기본 연산: if,for, while문, 산술 연산, 입출력 등

알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용됩니다.
알고리즘이 복잡해질수록 평균을 구하기 어려워져 최악의 경우로 알고리즘 성능을 파악합니다.

알고리즘의 성능 평가 Case

최악의 경우(Worst Case)

최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
빅오 표기법(O)을 사용

평균의 경우(Average Case)

여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우
세타 표기법(Θ)을 사용

최선의 경우(Best Case)

최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
오메가 표기법(Ω)을 사용

시간 복잡도 계산

    public static int func(int n) {
        int sum = 0; // 대입 연산 1회
        int i = 0;   // 대입 연산 1회
        
        for(i = 0; i < n; i++) { // 반복문 n+1회
            sum += i;            // 덧셈 연산 n회
        }
        for(i = 0; i < n; i++) { // 반복문 n+1회
            sum += i;            // 덧셈 연산 n회
        }
        return sum; // 리턴 1회
    }

위의 코드에서 연산 횟수는 주석과 같고, 총 연산 횟수는 4n+5 입니다.

빅오 표기법의 특징

상수항 무시

O(4n) -> O(n)

영향력 없는 항 무시

O(4n + 3) -> O(n)

위의 특징을 적용하면 이 알고리즘의 시간복잡도는 4n + 5 -> O(n) 입니다.

시간 복잡도 표기

이미지 출처

시간 복잡도	표기	설명	예시
상수 시간	O(1)	입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우	스택의 push와 pop 연산, HashMap과 HashSet의 삽입, 삭제, 탐색 (평균)
로그 시간	O(log n)	입력 크기가 커질수록 걸리는 시간이 로그 함수에 비례하여 증가하는 경우	이진 탐색
선형 시간	O(n)	입력 크기에 비례하여 시간이 증가하는 경우	for문, 연결 리스트의 순회
선형 로그 시간	O(n log n)	입력 크기와 로그 함수의 곱에 비례하여 시간이 증가하는 경우	퀵 정렬, 병합 정렬, 힙 정렬(우선순위큐)
2차 시간	O(n^2)	입력 크기의 제곱에 비례하여 시간이 증가하는 경우	이중 for문, 버블 정렬, 삽입 정렬, 선택 정렬
지수 시간	O(2^n)	입력 크기에 따라 시간이 지수 함수에 비례하여 증가하는 경우	피보나치 수열(재귀), 집합의 모든 부분 집합 생성