[Algorithm] 알고리즘 선택의 기준, 시간복잡도 (Big-O 표기법)

 

ㅇ 알고리즘이란?

컴퓨터가 특정 문제를 해결하는 방식이다. 물론 특정 문제를 해결하는 방식이 많이 있지만, 그중에서도 효율적인 방식을 찾는 것이 중요하다.

 

이러한 효율적인 알고리즘을 찾는 기준은 시간복잡도이다.

 

 

 

 

ㅇ 시간복잡도란?

알고리즘의 시간 복잡도는 성능을 나타내는 척도 중 하나로 알고리즘의 수행 시간을 나타낸다. 즉, 프로그램이 얼마나 많은 시간이 걸리는지를 나타내는 것이다.

 

다시 말하면, 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주한다.

 

시간복잡도가 큰 알고리즘은 작은 데이터에서도 느리게 동작하는 반면, 시간복잡도가 작은 알고리즘은 빠르게 동작한다.

 

 

 

 

ㅇ 시간복잡도 유형

이러한 시간복잡도를 정의하는 3가지 유형이 있다.

 

  ① 빅-오메가(Ω(n)) : 알고리즘의 실행시간이 최상일 때를 표기

 

  ② 빅-세타(𝜽(n)) : 알고리즘의 실행시간이 평균일 때를 표기

 

  ③ 빅-오(O(n)) : 알고리즘의 실행시간이 최악일 때를 표기

 

 

 

ㅇ 자주 사용되는 표기법?

알고리즘은 빅-오 표기법(O(n))을 기준으로 계산한다. 신뢰성이 떨어지는 오메가 표기법이나 평가하기 까다로운 세타 표기법에 비해 성능을 예측하기 용이하기 때문이다. 즉, 최악의 상황을 고려해야 한단 뜻이다.

 

 

 

 

ㅇ 빅-오(O(n)) 표기법에 대해 알아보자

https://www.bigocheatsheet.com/

 

① O(1)

 

데이터양(n)에 관계없이 일정하게 문제 해결에 하나의 단계만을 거친다.

 

class Main {
    public static void main(String[] args) {
        int[] arr = new int[1000000];
        arr[0] = 0;
        System.out.println(arr[0]);
    }
}

arr의 양의 크기에 상관 없이 해당 인덱스에 접근하여 값을 구할 수 있다.

 

 

② O(n)

데이터 양의 크기에 따라 시간이 1:1의 관계를 가진다. 즉, 데이터양이 많을 수록 처리 시간도 길어진다.

 

class Main {
    public static void main(String[] args) {
        int[] arr = new int[1000000];

        for(int i : arr) {
            System.out.println(arr[i]);
        }
    }
}

arr의 인덱스 값에 접근하여 arr의 모든 값을 출력하니, arr의 크기가 클수록 처리 시간도 길어진다.

 

 

③ O(N²)

문제 해결에 필요한 데이터양의 제곱만큼 수행된다.

 

class Main {
    public static void main(String[] args) {

        int star = 5;

        for(int i=0; i<star; i++) {
            for(int j=0; j<star; j++) {
                System.out.print("*");
            }
            System.out.println();
        }
    }
}

이중for문을 돌면서 *을 출력하기 때문에 이는 O(N²)의 시간 복잡도를 가진다.

 

 

④ O(log N)

로그 복잡도라 하며, 데이터양 또는 조건에 의해 처리시간이 감소하며, 이진트리, 이진검색이 이에 해당한다.

 

숫자 맞추기 게임을 예로 들어보자.

1부터 100까지의 수 중 80의 수를 찾는 게임이다.

우리는 먼저 가장 가운데 수를 입력할 것이다. 

 

1. 50을 입력하자.

> 50보다 큰 수이다.

(그렇다면 50보다 작은 수는 입력하지 않아도 될 것이다)

 

2. 75를 입력하자.

> 75보다 큰 수이다.

(75보다 작은 수는 입력하지 않아도 된다)

 

3. 87을 입력하자. (75와 100의 중간)

> 87보다 작은 수이다.

(87보다 큰 수는 검색하지 않아도 된다)

 

여기까지 결과는 75보다 크고 87보다 작은 수이다.

 

4. 81을 검색하자.

> 81보다 작은 수이다.

 

5. 80을 검색하자.

> 수를 맞췄다.

 

이처럼 경우의 수를 절반씩 줄여가면서 수를 찾는 방식이다.