Part 2-1-1. Big-O 표기법

 

 

Big-O 표기법

 

 

[Big-O 표기법을 사용하는 이유]

• 알고리즘의 성능을 객관적으로 측정하기 위하여 사용.
• 단순히 실행 속도를 비교하는 것으로 알고리즘 성능을 측정하는건 컴퓨터 실행 환경에 따라 차이가 있기 때문에 별로 좋지 못하다.
• 입력이 적은 구간과 많은 구간에서 성능이 확연히 차이가 나는 경우도 있을 수 있다.

 

 

[표기 방법]

1단계 : 수행 연산의 개수를 대략적으로 판단

• 어떤 연산이 1 개만 있다면 1 개
• 어떤 연산이 N 번 도는 for문 안에 있다면 N 개
• 어떤 연산이 N 번 도는 이중 for문 안에 있다면 N^2 개

 

2단계 : 대장만 남긴다.

public int Add(int N)
{
    int sum = 0;   //  1 번

    for (int i = 0; i < N; i++)  // N 번
        sum += i;
    
    for (int i = 0; i < 2 * N; i++)  // 4 * N^2 번 ⭐⭐ 얘가 가장 영향력이 크다. N^2니까.
      for (int j = 0; j < 2 * N; j++) 
          sum += 5;
    
    sum += 1234567;   // 1 번

    return sum;
}

 

1. 영향력이 가장 큰 대표적인 연산만 남긴다.
O(1 + N + 4 * N² + 1) = O(4 * N²)
가장 영향력이 큰 4 * N²번 연산만 남긴다.

 

2. 상수는 무시한다.
O(4 * N²) = O(N²)
위 코드의 성능은 최종적으로 O(N²) 라고 할 수 있다.

cf) O는 Order Of라고 읽는다.

 

거시적인 관점에서 보면, N 이 무한으로 커지면 커질 수록 N과 N²의 차이는 매우 커지게 된다. 따라서 대표적인 연산만 남기고 더 작은 연산들은 무시하는 것이다.

[크기 순서]

 

• N은 데이터(입력)의 크기가 된다.
• O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
• 👉 작을 수록 연산이 적게 걸린다는 것이니 가장 좋은 알고리즘이라는 뜻!
• O(N)까지는 보통 무리가 없다고 얘기한다.