Big-O 표기법

Big-O 표기법

 - 점근 표기법 이라고도 한다.

 - 알고리즘의 효율의 지표를 나타내는 표기법

 - 실행속도는 환경에 의존적이며, 입력 N의 크기에 따라 영향을 받을 수 있기 때문에 지표화 시키기 어려움.

   때문에 차선책인 Big-O 표기법을 사용함.

O(N^2)

 - O는 Order Of 라고 읽는다.

 

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

 - 일반 연산은 1개

 - N번 수행되는 반복문 안에 있다면 N개

 - N번 반복되는 중첩반복문에 있다면 N^2개

 

2) 대표 항목만 남긴다.

 - 차수가 가장 높은 것만 남기고, 상수 또한 삭제한다.

public int Test(int N)
{
    int result = 0;
    
    for(int i = 0; i < N; i++)
        result += i;
        
    for(int i = 0; i < 2 * N; i++)
        for(int k = 0; k < 2 * N; k++)
            result += 1;
            
    result += N;
    
    return result;
}

O(1 + N + 4 * N^2 + 1)
= O(4*N^2)
= O(N^2)