빅오(Big - O) 표기법 (점근 표기법)

• 빅오 표기법이란?

  • 알고리즘의 성능을 수학적으로 표기하는 표기법

  • 알고리즘의 시간, 공간 복잡도를 표현할 수 있다.

  • 데이터나 사용자의 증가율에 따른 알고리즘 성능을 예측하는 것이 목표이기 때문에, 2O(n) 과 같이 앞에 붙는 상수 2 같은 숫자들은 모두 없애고, O(n) 과 같은 형태로 작성한다.

  • 성능의 상한선(상한점근). 최악의 경우에 이 정도 속도는 보장되는 것을 뜻한다.

    점근? 점점 근접해지는 / 가까워진다는 의미.

• 표기법의 종류: 보통 아래의 표기법들을 표현 할 때, “O(n)의 시간복잡도를 가진다.” 라는 식으로 표현한다.

  O(1), O(n), O(log n)을 빠른 알고리즘이라 표현한다.

  • O(1)

    • 입력 데이터 크기에 상관없이, 언제나 일정한 시간이 걸리는 알고리즘.

      boolean F (int[] n){
        return (n[0] == 0)? true:false
      }
      

    • 그래프:

  • O(n)

    • 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘.

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

    • 데이터 = 시간 과 같은 비율로 올라간다.

    • 그래프:

  • O(n^2)

    • n스퀘어 라고 부른다. 이유는, n을 반복문으로 돌리면서, 내부에서 한 번 더 반복문을 돌리게 되는데, 이 때의 데이터를 보관할 때, 사각형과 같은 형태가 되기 때문.

    • 처리시간이 n의 가로/세로 면적만큼 소요되기 때문에, n의 값이 1씩 늘어날 때 마다 소요시간이 높아지게 된다.

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

    • 그래프:

  • O(nm)

    • O(n^2)와 비슷하게 내부에 반복문을 넣는데, n의 제곱이 아닌, m이라는 다른 변수의 값을 넣는다. O(n^2)과 혼동하기 쉽고, 그래프가 같다.

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

    • 그래프:

  • O(n^3)

    • O(n^2)과 비슷하지만, n의 제곱에 n을 한 번 더 곱한 만큼, 데이터가 늘어날 때 마다 더 급격하게 처리시간이 상승되는 특징을 가지고 있다.

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

    • 정육면체의 형태를 가짐.

    • 그래프:

  • O(2^n)

    • 함수를 호출 할 때마다, 바로 전전의 숫자를 더한 값을 얻기 위해, 매번 함수를 반복할 때 마다 두번씩 트리의 높이만큼 반복하는 특징을 가진다.

    • 위와 같은 특징으로, 데이터의 증가에 따라 처리시간이 현저하게 늘어나는 특징을 갖는다.

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

    • 그래프:

  • O(log n)

    • 이진검색 알고리즘이다.

    • 값의 중간값을 확인하여, 해당 값보다 원하는 값이 작은지 큰지를 비교하는 식으로 원하는 값을 찾아가는 식이다.

      1. 가운데 값부터 확인한다. 아래와 같은 정렬에서는 5.
      2. key 값과 비교하여 key의 값이 더 크다면, 작은 쪽의 값들은 모두 검색에서 제외된다.
      3. 값이 사라졌다면, 다시 한 번 가운데 값을 지정하여, key값과 비교한다.
      4. key의 값이 더 작다면, 큰 쪽의 값들을 검색에서 제외하여 결과가 나타난다.

    • 위와 같은 특징으로, 한 번 처리가 진행될 때마다 검색해야하는 데이터의 수가 줄어드는 알고리즘이다.

       int F (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 F(k,arr,s,m-1);
          }
          else {
            return F(k,arr,m+1,e);
          }    
        }
      

    • 그래프: