시간복잡도와 Big-O 표기

Big-O Notation(빅오표기법)

알고리즘의 성능을 수학적으로 표현해주는 표기법, 이걸로 알고리즘은 시간과 공간복잡도를 표현할 수 있다.

그리고 알고리즘의 실제 러닝타임을 표시하는것이아니라 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는것이 목표이기때문에 상수와 같은 숫자들은 모두 1이 된다. 

* 성능 순서(오른쪽으로 갈수록 성능이 안좋음)

   - O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) 

1. O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다. (Constant Time) [중요]

    - 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.

    - 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

   [예제코드]

/**
  * 해당 함수를 해석하면 인자로 받는 배열의 크기와 상관없이 언제나 일정한 속도로 값을 반환한다.
  * 이런 경우에 이 알고리즘을 "O(1)의 시간복잡도를 가진다"라고 표현한다.
*/
function(int[] n) {
    return (n[0] == 0) ? true : false;
}

* 위 이미지는 O(1)의 알고리즘을 그래프로 그린것이다. 그래프를 보면 가로축을 data의 크기, 세로축을 처리시간이라고 하자. 데이터가 증가함에따라 성능에 변함이 없는것을 볼 수 있다.

   [예제코드2]

/**
  * 해당 함수를 보자. 배열에 얼마나 많은 아이템이 있다 하더라도 알고리즘은 단순히 하나의 인덱스에만 접근하므로 그것은 O(1)이 된다.
*/
function(int[] arrayOfItems) {
    System.out.println(arrayOfItems[0]);
}

(1) 실제 예시
     - stack에 push하거나 pop할 때
     - hash table같은 경우에도 하나의 키에만 접근하므로 O(1)이다.
(2) 참고
     // 인자(=n)는 상관하지 않는다. (즉, 상수는 항상 무시)
     - nO(1) = O(1)
     - 2*O(1) = 10*O(1) = O(1)

2. O(n) : 입력 데이터의 크기에 비례해서 처리시간에 걸리는 알고리즘을 표현할 때 사용 (Linear Time) [중요]

    - 데이터양에 따라 시간이 정비례한다.

    - Linear search, for 문을 통한 탐색을 생각하면 된다.

   [예제코드]

/**
  * 아래 함수를 보면 n개의 데이터를 받으면 n번 Loop를 도니까 n이 하나 늘어남에 따라 처리도 한번씩 늘어나게 되므로 n의 크기만큼 처리시간이 걸리게 된다.
*/
function(int[] n) {
    for i = 0 to n.length
}

* 위 이미지는 O(n)을 그래프로 나타낸 것이다. 데이터가 증가함에 따라 비례해서 처리시간도 같이 증가한다. 언제나 데이터와 시간이 같은 비율로 증가한다.

   [예제코드2]

/**
  * 아래 함수를 보면 인자로 하나의 배열을 받았다고 생각하고 해당 배열에 있는 아이템을 모두 print한다고 생각하자. 그럼 배열이 아이템 개수만큼 Loop를 돌려야한다. 
  * 즉, 우리는 아이템의 개수만큼 엑세스 할 것이기 때문에 해당 예제는 O(n)이라 할 수 있다.
*/
function(int[] arrayOfItems) {
    for (int item : arrayOfItems) {
        System.out.println(item);
    }
}

(1) 실제 예시
     - traverse tree
     - traverse linked list
(2) 참고
     - nO(n) = O(n)
     - 2*O(n) = 10*O(n) = O(n)

3. O(n^2) : Quadratic Time

    - 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않음, 사용 X)

    - 해당 유형은 이중 Loop내에서 입력 자료를 처리 하는 경우에 나타난다. N값이 큰 값이 되면 실행 시간은 감당하지 못할 정도로 커지게 될 것이다.

    - 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱

   [예제코드]

/**
  * 아래 함수를 보면 n을 돌리면서 그 안에서 n으로 루프를 또 돌릴때 n square가 된다. (square = 제곱)
*/
function(int[] n) {
    for i = 0 to n.length
        for j = 0 to n.length
            print i + j;
}

* 위 그림을 보면 첫번째 Loop에서 n번 돌면서 각각의 엘리먼트에서 n번씩 또 도니까 처리횟수가 n을 가로 세로 길이로 가지는 면적만큼된다. 그러면 n이 하나 늘어날때마다 아래한줄 오른쪽한줄 n만큼씩 계속해서 생성된다. 즉, 데이터가 커지면 커질수록 처리시간에 부담도 커질것이다.

* 위 그림은 O n square를 그래프로 나타낸 것이다.  그래프를보면 처음에는 조금씩 상승하다가 나중에는 데이터를 하나 추가 할 때마다 그래프는 수직상승하게된다.

   [예제코드2]

/**
  * 아래 함수를 보면 하나의 array를 인자로 받고 Outer Loop와 Inner Loop가 있다. 즉, 10개의 아이템이 있으면 100번 엑세싱을하게 될 것이다.
  * 이것을 O(n^2) 라고 한다.
*/
function(int[] arrayOfItems) {
    for (int firstItem : arrayOfItems) {
        for (int secondItem : arrayOfItems) {
            int[] orderedPair = new int[]{firstItem, secondItem};
            System.out.println(Arrays.toString(orderedPair));
        }
    }
}

(1) 실제 예시
     - Insertion Sort(삽입정렬)
     - Bubble Sort(거품정렬)
     - Selection Sort(선택정렬)
(2) 참고
     - nO(n^2) = O(n^2)
     - 2*O(n^2) = 10*O(n^2) = O(n^2)

4. O(nm) : (Quadratic time) - 2

   [예제코드]

/**
  * n을 m만큼 돌린다.
*/
function(int[] n, int[] m) {
    for i = 0 to n.length
        for j = 0 to m.length
            print i + j;
}

* 위 그림을 참고하자. 해당 표기법은 O(n^2)표기법과 비슷하지만 해당 표기법은 n은 엄청크고 m은 아주 작을수도 있기 때문에 변수가 다르다면 빅O표기법에도 반드시 다르게 표시하여야한다.

* O(nm) 표기법은 데이터가 증가할수록 수직상승하는 모양으로 된다.

5. O(n^3) : (polynomial / cubic time)

   [예제코드]

/**
  * n의 제곱에 n을 한번 더 돌리면 n의 세제곱이 된다. 
  * 아래 코드와 같이 Loop를 n을 가지고 삼중으로 돌리면 n의 세제곱이 될 것이다.
*/
function(int[] n) {
    for i = 0 to n.length
        for j = 0 to n.length
            for k = 0 to n.length
                print i + j + k;
}

* O(n)일 경우에는 직선이고 O(n^2)이면 면적이된다. 그리고 O(n^3)이면 n의 제곱을 n만큼 더 돌리니까 큐빅모양이 될 것이다.

* O(n^3)은 O(n^2)와 비슷한 양상을 보이지만 데이터가 늘어남에 따라 가로세로의 높이까지 더해지니까 아무래도 데이터가 증가함에따라 더 급격하게 처리시간이 늘어나는것을 위의 그래프로 확인할 수 있다.

6. O(2^n) : Fibonacci (Exponential Time) -> 해당 표기법은 피보나치수열과 유사하다.

* 위 그림은 유명한 피보나치의 나선형 그림이다.

* 예제를 보기전에 피보나치수열에 대하여 알아보자. 피보나치수열이란 "바로 전 두 숫자를 더해서 다음 숫자를 만드는 패턴이다." ex) 1, 1, 2, 3, 5, 8, 13, 21.... 

   피보나치 수열의 일반항을 Fn이라고 하면, F1=1, F2=1이다. 그리고 F3=2인데 이것은 F1+F2를 계산한 값이다. F3=F1+F2 이고, F4=F2+F3이다. 즉, 1+1=2, 1+2=3, 2+3=5 ... 이다.

   [예제코드]

/**
  * 함수를 호출할때 마다 바로 전의 숫자랑 전전 숫자를 알아야 더할 수 있기 때문에 해당 숫자를 알아내기 위하여
  * 하나 뺀 숫자를 가지고 재귀호출을하고 두개 뺀 숫자를 가지고 한 번 더 이렇게 매번 함수가 호출될 때마다
  * 두번 씩 또 호출을 하게 되는데 그걸 아래 이미지처럼 트리의 높이만큼 반복하는 것이다.
*/
function(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = function(n-1, r) + function(n-2, r);
}

* 아래 이미지를 보면 피보나치수열을 그래프로 나타낸것이다. 즉, O(n^2)이나 O(n^3)보다도 데이터의 증가에 따라 처리시간이 현저하게 늘어나는것을 확인할 수 있다.

7. O(m^n) : m개씩 n번 늘어나는 알고리즘을 표현(Exponential Time) 즉, 2대신에 m을 써서 표현하면 된다.

8. O(log n) : (Binary search tree access(이진 검색), search(검색), insertion(삽입), deletion(삭제)) [중요]

    - 데이터양이 많아져도, 시간이 조금씩 늘어난다.

    - 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.

    - 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

    - 만약 입력 자료의 수에 따라 실행 시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.

   [예제코드]

/**
  * (1) O(log n)의 대표적인 알고리즘은 이진검색이다. 아래 정렬된 값들중에서 6이라는 값을 찾아보기로한다.
  * (2) 정렬이 되어있으니까 이진검색을 하려면 우선 가운데값인 5를 찾아서 키값과 비교한다. 
  *      즉, 키값이 가운데값인 5보다 더크므로 오른쪽에 있다. ( 이제부터 앞에 1,2,3,4,5는 제외시킨다. )
  * (3) 뒤쪽의 데이터 6,7,8,9중에 중간값인 7을 찾아서 키값과 비교한다. 키값이 더 작으니까 왼쪽(=앞쪽)에 있다고 추측할 수 있다. 
  *      (이제부터 뒤쪽에 7,8,9 데이터는 안봐도 되므로 제외시킨다.)
  * (4) 위의 과정이 끝나면 찾는값인 6이 남아있다. 
  * (5) 이렇게 한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 알고리즘을 O(log n)알고리즘이라 한다.
*/
function(k, arr, s, e) {
    if (s > e) return-1;
    m = (s + e) / 2;  // 주어진 range에 중간값을 찾는다.
    if (arr[m] == k) return m;

    // 찾는값이 중간값보다 작으면 중간지점 바로 전까지 range를 지정해서 다시 호출
    else if (arr[m] > k) return function(k, arr, s, m-1);  

    // 찾는값이 중간값보다 크면 끝에서 다시 찾아야 하므로 가운데 번호 + 1부터 끝까지 호출하면 한번 함수가 호출될때마다
    // 중간값을 기준으로 절반은 검색영역에서 제외시켜버리기 때문에 순차검색에 비교해서 속도가 현저하게 빠르다.
    else return function(k, arr, m+1, e);   
}

* 아래 그래프를 참고하면 O(log n)이 O(n)보다도 훨씬 성능이 좋으며 그리고 데이터가 증가해도 성능이 크게 차이나지 않는다.

   [예제코드2]

// 예를 들어 총 8개의 Item이 있으면 log 8 = log2^3 = 3 이므로 3번의 계산이 이루어졌다.

(1) 참고
     - nO(log n) = O(log n)
     - 2*O(log n) = 10*O(log n) = O(log n)

9. O( Sqrt(n) ) : Square Root  // Square Root는 제곱근이라고 한다.

    - 아래 그림을 참고해보자. 예를들어 100의 제곱근은 10이다. (10 x 10 = 100) 9의 제곱근은 3이다.(3 X 3 = 9) 그리고 만약 n=4라면 해당 n을 정사각형에 채워서 맨위의 한줄이 제곱근이다.(sqrt(n) = 2)

    - 또한 아래 그림을 참고하면 n=9일 때 위와 마찬가지로 맨 위의 한줄이 제곱근이 되므로(sqrt(n) = 3)이다.

10. O(nlog n) : Quick Sort(빠른 정렬), Merge Sort(병합 정렬), Heap Sort(힙 정렬)

     - 데이터양이 N배 많아 진다면, 실행 시간은 N배 보다 조금 더 많아진다. (정비례 하지 않음)

     - 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두배로 늘어나면 실행시간은 2배보다 약간 더 많이 늘어난다.

* 위 그림의 숫자가 있는 그래프는 Merge Sort에 대한 과정을 나타낸 것이다.  과정을 설명하자면..

  (1) 6 4 3 1을 6 4와 3 1로 분할

  (2) 6 4와 3 1을 분할한다. (6 4를 6과 4, 3 1을 3과 1)

  (3) 각자의 아이템을 비교하여 6과 4는 4 6으로, 3과 1은 1 3으로 정렬하는 과정을 O(nlog n)의 과정이라한다.

[마무리]

Big-O에서는 상수는 과감하게 버린다.!!

ex) 예를 들어 아래 코드를 확인해보자. 해당 코드는 시간복잡도가 얼마일까?

   [예제코드]

/**
  * 이건 n만큼씩 두번돌리니까 O(2n)만큼의 시간이 걸린다.
  * 그런데 빅오표기법에서는 O(2n) => O(n) 으로 표시한다.
  * 이유는 빅오표기법은 실제 알고리즘의 러닝타임을 측정하기 위해 만든것이 아니라 
  * 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기위해 만들어진 표기법이기 때문이다.
  * 상수는 고정된 숫자니까 증가율에 영향을 미칠때 언제나 고정된
  * 상수만큼씩만 영향을 미치게때문에 여기서 증가하지 않는 숫자는 신경쓰지 않겠다는 뜻이다.
*/
function(int[] n) {
    for i = 0 to n.length
        print i
    for i = 0 to n.length
        print i
}

/**
  * 마찬가지로 O(n^2 + n^2) => O(n^2) 이렇게 표기한다.
*/
function(int[] n) {
        for i = 0 to n.length
	    for j = 0 to n.length
	        print i + j;
        for i = 0 to n.length
	    for j = 0 to n.length
	        prit i + j;    
}