빅 오 표기법(Big-O Notation)

빅오 표기법(Big-O Notation)

 

• 알고리즘의 시간 효율성과 메모리 효율성을 나타냄
• 빅오메가 : 하한 점근, 최선의 경우 표기법
• 빅세타 : 상한/하한점근, 정확한 성능 표기법
• 빅오 : 가장 최악인 상황에서 최소 보장되는 성능, 효율성을 상한선 기준으로 표기(최악의 효율)
• 알고리즘 효율성은 값이 클수록, 비효율적임을 의미함
• 알고리즘의 실제 러닝타임이 아니라, 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 나타내는것
• 상수는 항상 제외한다 O(2n) 인경우 O(n)으로 표기해야 맞는것이다
  

 

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

   O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) < O(2ⁿ) 

HashSearch < Binary Search < Sequential Search < Quick Sort < 구구단 출력 함수 <Floyd-Warshall < 피보나치 수열

 

 

 

O(1) : constant time, 언제나 일정한 속도, HashSearch 

ex)

F(int[] n){

       return (n[0] == 0)? true : false;

}

// n의 크기에 상관없이 언제나 일정한 속도로 결과를 반환

 

 

가로축 : data의 크기

세로축 : 처리시간

 

데이터가 증가함에 따라 처리시간은 항상 일정한 것을 볼 수 있다

 

 

 

 

 

 

O(logN) : logarithmic time, 이진탐색(Binary Search)

ex)

F(k, arr, s, e){

       if ( s > e ) return -1;

       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);

}

 

// 이진 탐색

 

가로축 : data의 크기

세로축 : 처리시간

 

데이터가 증가하여도 처리시간이 크게 늘어나지 않는다

 

 

 

 

 

 

O(n) : linear time, n번만큼 동작하는 루프1개, sequential search

ex)

F(int[] n){

       for i = 0 to n.length

              print i

}

// n개의 data를 받으면 n번 만큼의 loop를 돌게된다, 즉 n의 크기에 비례해서 처리시간이 늘어남

 

 

가로축 : data의 크기

세로축 : 처리시간

 

데이터가 증가함에 따라 비례해서 처리시간도 증가함, 언제나 데이터와 시간이 정비례한다

 

 

 

 

 

 

O(nlogn) : log linear, Quick Sort

데이터가 증가함에 대해 처리 시간은 정비례보다 약간 더 많이 증가를함

 

가로축 : data의 크기

세로축 : 처리시간

 

데이터양에 따라 걸리는 시간은 제곱에 비례함

 

 

 

O(n²) : quadratic time, n번만큼 동작하는 이중 루프, 구구단 출력 함수

ex)

F(int[] n){

      for i = 0 to n.length

            for j = 0 to n.length

                      print i + j;

}

// n개의 data를 받으면 n번 만큼의 loop를 돌고 이것을 이중으로 함(이중루프)

 

가로축 : data의 크기

세로축 : 처리시간

 

데이터양에 따라 걸리는 시간은 O(n²)과 거의 유사하다

 

 

 

 

 

 

 

 

O(n³) : cubic time, n번만큼 동작하는 삼중 루프, Floyd-Warshall

ex)

F(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(2ⁿ) : exponential time, 피보나치 수열 

ex)

F(n, r){

      if (n <= 0) return 0;

      else if( n == 1) return r[n] = 1;

      return r[n] = F(n -1, r) + F(n - 2, r);

}

 

 

가장 성능이 안 좋다.