[자료구조] BIG-O 표기법 계산 방법

BIG-O 표기법은 수행되는 연산(산술, 비교 등)의 개수를 대략적으로 판단하는 지표로 사용된다.

BIG-O 표기법은 단순이 연산을 계산하는 것 이아니라 데이터가 늘어남에 따라서 얼마나 연산이 늘어나냐가 중요하기 때문에 단순한 상수등은 생략을 하게된다.

BIG-O를 나타낼 때는 O라고 표시하며 Order of라고 읽는다.

대략적인 계산

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

        //Add2 = O(N +1)
        int Add2(int n)
        {
            int sum = 0;

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

        //Add3 = O(N^2 + 1)
        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;
        }

Add = O(1)

Add2 = O(N +1)

Add3 = O(N^2 + 1)

 

영향력이 가장 큰 대표 항목만 남기고 삭제

        //Add4 = O(1 + 4 * n^2 + 1)
        int Add4(int n)
        {
            int sum = 0;

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

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

            sum += 1;

            return sum;
        }

Add4 = O(1 + 4 * n^2 + 1)

= O(4*n^2)

= O(n^2)