[Algorithm] 빅오 표기법과 시간 복잡도의 개념 및 예제

728x90

알고리즘에서 중요한 속성

1. 정확성 : 주어진 입력을 모두 처리하며 올바르게 출력해야 한다.

2. 효율성 : 문제를 효율적으로 해결해야 한다. 두 가지 변수로 측정

- 시간 복잡도 : 알고리즘이 얼마나 빠르게 결과를 출력하는지 측정, 입력 크기 n에 대한 시간 함수 T(n)으로 표현

- 공간 복잡도 : 원하는 결과를 얻기 위해 알고리즘이 얼마나 메모리를 사용하는지 측정, 입력 크기 n에 대한 메모리 사용 함수 S(n)으로 표현

빅오 표기법 (big-O)

- 점근적 분석의 한 방법

- 수학적 정의

- cg(n)은 모든 n >= n0에 대해 f(n)의 상한이다.

- 최고차항의 차수로 표현하고 계수와 낮은 차수의 항은 무시한다.

(예시) n^2 + n = O(n^2)

시간 복잡도

알고리즘에 주로 나오는 시간 복잡도.

시간이 커지는 순서로 나열했습니다 :)

1. 상수 시간 O(1)

입력 크기와 상관없이 고정된 시간으로 계산한다면 알고리즘이 상수 시간(constant time)에 실행된다고 한다.

- 배열의 n번째 원소에 접근

- 스택에 push/pop

- 큐에 삽입/삭제

- 해시 테이블의 원소에 접근

2. 선형 시간 O(n)

알고리즘의 실행 시간이 입력 크기에 정비례

- 배열에서 검색, 최솟/최댓값 찾기 등 연산

- 연결 리스트에서 순회, 최솟/최댓값 찾기 등 연산

3. 로그 시간 O(logn)

알고리즘의 실행 시간이 입력 크기의 로그에 비례.

알고리즘의 각 단계에서 입력의 상당 부분(절반)을 방문하지 않고 지나간다.

- 이진 탐색(binary search) 알고리즘

4. N 로그 N 시간 O(nlogn)

알고리즘의 실행 시간이 입력 크기와 입력크기의 로그 곱에 비례.

이런 알고리즘은 입력의 절반(또는 일부)으로 나눌 때마다 각 부분을 독립적으로 처리

- 병합 정렬(merge sort)

- 퀵 정렬(quick sort) - 평균적인 성능, 최악의 시간 복잡도는 O(n^2)

- 힙 정렬(heap sort)

5. 이차 시간 O(n^2)

알고리즘의 실행 시간이 입력 크기의 제곱에 비례

이런 알고리즘은 각 원소를 다른 모든 원소와비교

- 버블 정렬(bubble sort)

- 선택 정렬(selectrion sort)

- 삽입 정렬(insertion sort)

6. 지수 시간 O(2^n)

입력 데이터들의 원소들로 만들 수 있는 모든 부분 집합을 생성

7. 계승 시간 O(n!)

입력 데이터의 원소들로 만들 수 있는 모든 순열을 생성

알고리즘 속 함수 실행 시간 도출

- 반복문 : 반복문 내 수문의 실행 시간과 반복 횟수의 곱. 시간 복잡도는 O(n)

- 중첩 반복문 : 모든 반복문 크기의 곱과 반복문 내 구문의 실행 시간을 곱한 것. 반복문 수를 c라고 할 때 시간 복잡도는 O(n^c)

- 연속 구문 : 연속된 구문의 실행 시간을 모두 더한다.

- if-else 구문 : if나 else 중 실행 시간이 더 많이 걸리는 블록을 선택, 나머지는 무시.

- 로그 구문 : 각 반복마다 입력 크기가 일정하게 감소. 시간 복잡도는 O(logn)

시간 복잡도 예제

int f(int n){
	int m = 0;
    for (int i = 0; i < n; i++) {
    	for(int j = 0; j < n; j++){
        m += 1;
        }
    }
    return m;
}

> 시간 복잡도 : O(n^2)

int f(int n) {
	int i, j, m = 0;
    for (i = 0; i < n; i++) {
    	for (j = 0; j < i; j++) {
        	m += 1;
        }
    }
    return m;
}

> 시간 복잡도 : O(n + (n-1) + (n-2) + ... + 1) == O(n(n+1)/2) == O(n^2)

int f(int n) {
	int i, m = 0;
    i = 1;
    while (i < n) {
    	m += 1;
        i = i * 2;
    }
    return m;
}

> 시간 복잡도 : O(logn)

> 문제 공간을 매번 절반으로 나눔

int f(int n)
{
    int i, j, k, m = 0;
    for (int i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            m += 1;
        }
    }
    for (i = 0; i < n; i++)
    {
        for (k = 0; k < n; k++)
        {
            m += 1;
        }
    }
    return m;
}

> 시간 복잡도 : O(n^2) + O(n^2) = O(n^2)

> 두 반복문은 연속적이므로 두 그룹의 복잡도를 더한다.

int f(int n)
{
    int i, j, m = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < sqrt(n); j++)
        {
            m += 1;
        }
    }
    return m;
}

> 시간 복잡도 : O(n*√n) = O(n^(3/2))

int f(int n)
{
    int i, j, m = 0;
    for (i = n; i > 0; i /= 2)
    {
        for (j = 0; j < i; j++)
        {
            m += 1;
        }
    }
    return m;
}

> 시간 복잡도 : O(n + n/2 + n/4 + n/8 + n/16 + ...) == O(n)

> 중첩 반복문에서는 내부 반복문에서 시간 복잡도를 계산