[알고리즘] 시간 복잡도와 Big-O 대해서 간단한 예제

 

알고리즘이란?

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전] 

즉, 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임입니다. 

 

 

점근 표기법이란?

알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법입니다. 
점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다.

 

빅오(Big-O)표기법

빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것에 대한 표기법

 

빅 오메가(Big-Ω) 표기법

빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기법

 

 

 

빅오(Big-O)표기법 자세히 알아보기

빅오 표기법은 불필요한 연산을 제거하여 알고리즘분석을 쉽게 할 목적으로 사용된다.

• Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다
• 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
• 공간복잡도는 알고리즘이 실행될때 사용하는 메모리의 양을 나타낸다.
  요즘에는 데이터를 저장할 수 있는 메모리의 발전으로 중요도가 낮아졌다.

 

 

시간 복잡도란?

입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!

입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.

입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?

 

O(1) : 상수

매개변수 n의 길이 만큼 반복하지만 n은 인덱스 0이라는 상수로 되어 있어 입력에 관계없이 복잡도는 동일하게 유지된다.

public void bigO1(int[] n) {
    for (int i = 0; i < n.length; i++) {
        System.out.println(n[0]);
    }
}

 

 

O(N) : 선형

입력값의 n의 길이 만큼 반복한다. 즉, 입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.

public void bigON(int[] n) {
    for (int i = 0; i < n.length; i++) {
        System.out.println(n[i]);
    }
}

 

 

O(N^2) : Square

반복문안에 반복문이 n의 길이 만큼 반복하기 때문에 n x n  = N^2 이다. 

public void bigON2(int[] n) {
    for (int i = 0; i < n.length; i++) {
        for (int j = 0; j < n.length; j++) {
            System.out.println(i + j);
        }
    }
}

 

 

O(log n)

주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다. 다음은 이진검색의 예이다.

public int bigOLogN(int k, int[] arr, int s, int e) {
    if (s > e) {
        return -1;
    }
    int m = (s + e) / 2;
    if (arr[m] == k) {
        return m;
    } else if (arr[m] > k) {
        return bigOLogN(k, arr, s, m - 1);
    } else {
        return bigOLogN(k, arr, m + 1, e);
    }
}

 

 

o(2ⁿ)  : Fibonacci

해당 숫자를 알아내기 위해서 1뺀 수자를 가지고 한번 재교체를 하고 2개 뺀 숫자를 가지고 한번 더 이렇게 매번 함수가 호출될 때 마다 두번 씩 또 호출한다.  o(2ⁿ) 는 데이터의 증가에 따라 처리시간이 현저하게 늘어나는 복잡도를 가지고 있습니다.

public int bigO2ⁿ(int n, int[] r) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return r[n];
    }
    return r[n] = bigO2ⁿ(n - 1, r) + bigO2ⁿ(n - 2, r);
}

 

전체코드는 아래 링크에서 확인 가능합니다.

GitHub - whitewise95/java_dataStructure_and_collection: 자바와 자료구조 그리고 콜렉션 등을 연습하는 소스입

 

Big-O 표기법을 나타내는 표

 

아래표는 실행시간이 빠른순으로 입력 N값에 따른 서로 다른 알고리즘의 시간복잡도이다.

Complexity	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N log N)	0	20	461
O(N^2)	1	100	10000
O(2^N)	1	1024	1267650600228229401496703205376
O(N!)	1	3628800	화면에 표현할 수 없음!

출처 :  https://blog.chulgil.me/algorithm/

 

 

 

 

 

참고한 블로그 및 영상 

 

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

알고리즘 복잡도와 빅 오 표기법