[알고리즘 or 자료구조] 빅오 표기법이란 무엇인가?

 

1. 빅오 표기법(Big - O notation)이란?

 

빅오 표기법이란 알고리즘의 시간 복잡도나 공간복잡도를 나타내는 수학적 표현 방식이다.

특히 알고리즘의 최악(worst)성능을 표현하는데 자주 사용된다.

이 표기법은 입력 크기가 커질 때 알고리즘의 실행시간이나 필요한 메모리 공간이 어떻게 증가하는지

설명하기 위해 자주 사용되는 것 이다.

 

 

2. 최적 , 평균 , 최악의 성능이란?

 

 

 

간단한 예제 코드가 있다.

 

이 예제코드는 크기가 100의 배열에 1~10까지의 값들을 100번 채워 넣는다.

 

그 후 array의 배열 중 5가 있다면 몇번만에 찾았는지 표기하는 것 이다.

 

 

나의 경우는 8번만에 찾은걸 볼 수 있다.

 

● 최적의 성능 일때

array[0]번째가 5가 있어 1번만에 찾았을 경우 최적의 성능이라고 볼 수 있다.

 

● 보통의 성능 일때

 

array의 100개까지 있음으로 평균 50번안에 값들을 찾았을 경우 보통의 성능이라고 할 수 있다.

 

● 최악의 성능 일때

 

array가 100개 까지 있지만 랜덤한 숫자가 5가 없고 99번째에 있거나 아예 없을 경우

array의 모든 값들을 순회하여야만 한다.

이럴 경우 최악의 성능이라고 한다.

 

 

즉 빅오 표기법은 이러한 연산결과가 최악일 경우를 가정하여 복잡도를 계산하는데 

주로 사용되는 표기법이다.

 

여기서 알아야할것은 빅오 표기법은 연산의 결과를 표시 해주는것이 아니라연산 횟수를 계산 해주는 것 이다.

 

즉 어떤 알고리즘이 연산횟수가 가장 빠른지 알고싶을 때 쓰는 것이 빅오 표기법이다.

 

 

 

 

 

3. 빅오 표기법 방식

 

일반적으로 빅오 표기법은 T(n)이라교 표시 될 수 있다.

T는 시간을 뜻하고 n은 함수의 들어갈 매개 인자를 뜻한다.

 

예를 들어보자 ,

 

T(n) = n^2 + n + 1

 

이러한 시간 복잡도가 있다.

 

n = 1000 일 때 T(n)의 값은 1,001,001 이고 이중에서 첫번 째 항인 n^2의 값이 전체의 약

99.9%인 1,000,000이고 두 번째 항의 값이 1000으로 계산된다.

즉 두번 째 항은 0.1%를 밖에 차지 하지 않는 것 이다.

 

이렇게 n^2이 99.9%차지하고 n +1의 값은 0.1% 밖에 차지 하지 않는다.

 

즉 이러한 0.01%의 값은 의미가 없으며 이러한 퍼센트의 값은 고려하지 않고

오직 큰 항만의 연산결과만을 고려하는 것이 빅오 표기법이다.

 

즉 빅오 표기법으로 계산하면 T(n^2)가 되는 것 이다.

 

 

 

빅오 표기법은 이러한 그래프로 구현된다.

또한 빅오표기법은 T(n)에서 파생되어 그래프의 있는 공식의 값을 대부분 알고리즘에서 사용하고 있다.

 

그렇다면 저것이 무슨 의미를 하는 것인지 알아보자.

 

 

1. O(1)

 

O(1)의 빅오표기법인 경우는 어떠한 함수에 값을 넣었을때 연산횟수가 반드시 1번에 끝난다는 것 이다.

 

 

 

즉 코드로 보자면 이렇다.

이 코드는 이 array의 함수를 호출하면 반드시 0번쨰의 배열의 값을 준다.

 

어떠한 결과를 넣어도 반드시 1번의 연산만 한다.

 

이러한 것을 빅오 표기법으로 O(1)이라고 한다.

 

 

2.O(log n)

 

O(log n)의 경우 로그함수의 특징을 따 만든 표기법이다.

 

로그함수의 특성상 일정한 횟수가 지나면 아주 천천히 올라가는것이 특징인데

이 표기법도 마찬가지이다.

 

이러한 O(log n)의 경우 보통 이진탐색이 주로 활용된다.

 

 

코드는 이렇다.

 

 

 

이진 탐색의 경우 이렇게 low , high ,mid로 나눠서 찾는 값이 mid의 기준에 따라서 달라지게 된다.

 

이렇게 이진탐색은 어떠한 값이 들어와도 연산 횟수가 천천히 증가 되는걸 확인 할 수 있다.

 

계산 방식은 이렇다.

 

O(logn)에서 logn에 8이 들어왔을 경우

logn에서 n은 2로 표기한다.

 

O(8) = 3이 나오게 된다. 

 

계산 결과는 다음과 같다 O(logn)에서 8이 들어 왔음으로

8은 2^3이다. 즉 2^3 = 8이 됨으로

결과 값은 O(logn) = 3이 된다.

 

즉 8의 값을 넣었을 경우 연산횟수는 3번이 된다는 뜻이다.

 

만약 8000의 값이 들어왔다 하더라도 300번의 연산밖에 하지 않는 것 이다.

 

 

 

이진탐색의 조건은 항상 정렬된 배열값이 있어야 한다.

 

 

3. O(n)

 

O(n)은 모든 원소의 값들을 한번씩 순회하는 것 이다.

 

즉 우리가 사용하는 for문의 경우 이 O(n)이 사용된다.

 

 

 

즉 이 메서드는 항상 모든 배열의 값들을 출력한다.

O(n)은 모든 원소의 값들을 순회하는 빅오 표기법이다.

 

O(n)에 100을 넣으면 

O(100) = 100 

O(1000) = 1000

O(10000) = 10000

즉 이렇게 배열의 값 100개를 넣으면 연산 횟수는 100번

1000을 넣으면 연산횟수는 1000번이 된다.

 

 

4. O(n log n)

 

O(n log n)은 정렬알고리즘 즉 , 분할 정복 알고리즘의 많이 사용된다.

 

O(n log n)의 8을 넣었을 경우

n = 8임으로

O(8) = O(logn) = 3 * n이 됨으로 연산 결과는 24가 나오게 된다.

 

 

 

5. O(n^2)

 

O(n^2)는 2중 포문이 들어간 경우 O(n^2)라고 표시한다.

 

정렬 알고리즘 , 버블 알고리즘 , 브루트 포스 알고리즘이 대표적이다.

 

 

 

즉 이렇게 2중 for문이 들어간 경우 O(n^2) 빅오 표기법을 채택할 수 있다.

 

계산 방법은 O(n^2) = O(10) = 100이 된다.

 

즉 10번 배열의 크기를 넣었을 경우 총 연산 횟수는 100회가 되는 것 이다.

 

 

나머지 O(n^3) O(n^2)여러가지 알고리즘이 있지만 

보통은 O(n^2)까지의 알고리즘을 선택한다.

그 이상은 최악의 알고리즘 이기 때문이다.