[C++ 자/알 Note] Big-O 표기법

Big-O 표기법 사용이유

알고리즘의 성능 비교를 위해 Big-O 표기법을 사용한다

 

Big-O 표기법 사용법

1단계. 대략적인 계산

2단계. 최고차항 계수만 남기고 상수도 버린다

 

Big-O 표기법 사용법 예시

int Add(int n)
{
    return n + n;
}// O(1)

 

int Add2(int n)
{
    int sum = 0;

    for(int i = 0; i < n; i++)
    {
        sum += i;
    }

    return sum;
}// O(N)

 

int Add3(int n)
{
    int sum = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            sum += 1;
        }
    }

    return sum;
}// O(N^2)

 

int Add4(int n)
{
    int sum = 0;

    for(int i = 0; i < n; i++)
    {
        sum += i;
    }// O(N)

    for(int i = 0; i < 2 * n; i++)
    {
        for(int j = 0; j < 2 * n; j++)
        {
            sum += 1;
        }
    }// O(4N^2)

    sum += 1234567;// O(1)

    return sum;
}// O(4N^2 + N + 1) -> O(N^2)

 

Big-O 표기법 그래프

 

log 함수

로그 함수는 매번 절반 씩 줄어드는 것이 핵심이다

또한, 프로그래밍에서 밑은 대부분 2이기 때문에 생략을 해서 표현한다