Big-Oh 표기법(Big-Oh notation)

앞에서 입력자료의수 N에 대해서 그 실행시간 함수 T(N)은 일정한 유형이 있음을 알아보았는데요 실제로는 이유형에 상수가 곱해지고 더해집니다.

실행시간에 대해서 오해하기 쉬운점은 나쁜유형의 알고리즘이라도 효율석있게 만들면 좋지 않을까? 인데 물론 잘만 프로그래밍한다면 바꿀수는 있지만 알고리즘 자체를 변경하는것은 불가능 합니다. 효율적인 프로그래밍은 유형에 곱하거나 더해지는것을 작게 하는것분 획기적인 시간단축을 위해서는 알고리즘 자체를 개선해야 합니다.

하나의 알고리즘을 여러사람이 프로그래밍 한다면 실행 결과의 함수는 모두 다를 뿐더러 이 알고리즘은 추상적인 방법인데 비해 프로그래밍은 정말 많은 변수가 있기때문에 서로다른 실행시간을 가져옵니다. 그래서 경험적으로 알고리즘 성능을 판단하는것은 옳지 못하기 때문에 이런 알고리즘 성능을 객관적으로 표현하는 기준이 바로 O표기법 입니다.

O 표기법의 정의는

만약 실행 시간 함수T(N)이 N0보다 큰 N에 대하셔 항상 C0F(N)보다 작거나 같은 C0와 N0가 존재한다면 T(N)은 O(F(N))이라고 합니다.

즉 N>=N0인 모든 N에 대하여 T(N)<=C0F(N)이 만족하면 T(N)=O(F(N))입니다.

실제 실행함수 T(N)이 같는 상수는 프로그래머의 능력에 따라 달라질수 있는 것이기 때문에 순수한 알고리즘 성능표시를 위해 상수요소를 없어야 하는데 이 상수 요소를 없앤 입력 자료수 N에 따른 실행시간만 나타낸것이 바로 O 표기법입니다 

이 O표기법은 정의상 알고리즘 실생시간의 상한을 나타냅니다. 실행시간의 상한은 최악의 경우 에 해당한다는것도 알아둡시다. 즉 O표기법은 최악의 경우에 대한 입력 자료수 N에 대한 실행시간 함수 관계입니다.

예시로

T(N) = 3*N*N+1

T(N)은 4*N*N보다는 N이 1보다 큰 경우에 항상 작으므로 상수 4를 떼버리고 O(N^2)이 라고 말할 수 있습니다. 또한 4*N*N*N도 O(N^3)라고 말할수 있고 더 큰수도 가능하지만 이렇게 큰함수만 잡는것은 알고리즘 성능을 표헌하는데 큰 의미가 없습니다.

일반적으로 T(N)이 N의 다항식으로 나타날 떄는 최고차항만 의미가 있습니다. 그래서 T(N)이 최고차가 m이라면 O(N^m)이라고 말할수 있습니다.

하지만 O표기법을 과신하는것도 문제 가 있습니다

첫번째로 O표기법은 실행시간의 상한을 제공하기 때문에 실제로는 실행시간이 작을수도 있습니다

두번쨰로 알고리즘이 실행시간이 상한을 하는것은 실제 운용상 거의 나타나지 않습니다.

세번째로는 미정의 상수 C0는 충분히 작아야 합니다.

네번째로는 미정의 상수 N0역시 충분히 작아야 한다는 점 입니다

예를 들어 가장 빠른 정렬 알고리즘이라고 알려져 있는 퀵정렬의 경우 그 실행시간은 O(N^2)입니다 O표기법은 최악의 경우 실행시간의 상한을 나타내기 때문에 실제의 일반적인 경우 실행시간은 훨씬 적습니다. 퀵 정렬은 일반적으로 NlogN의 실행시간을 가져 매우 빠른 속도를 가집니다.

결론은 O표기법은 최악의 경우라도 넘지않는 실행시간의 함수이기 떄문에 일반자료에 대한 실행시간 보다는 훨씬 큰 값을 가진다. 일반적인 경우에는 매우 뛰어난 속도를 가지지만 최악의 경우에만 극도로 성능의 좋지 않는 알고리즘의 경우 O표기법은 과장되게 성능이 나쁜것으로 판단합니다.

--후일 추가 내용 다른 표기법과 시간적 공간적 소요량