점근적 표기법
ko.khanacademy.org
*이 글은 위 링크의 글을 개인공부를 목적으로 필사하거나 요약한 글입니다.
알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존합니다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.
알고리즘의 실행 시간, 두 부분으로 나누어 생각하기
1. 선형탐색, 이분탐색에선 입력값의 크기가 클수록 값을 찾아내기까지 추측의 횟수가 많아짐을 알수있습니다. 이처럼 입력값의 크기에 대한 함수를 기준으로 알고리즘 실행 시간을 생각할 수 있습니다.
2. 입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아보는 것이 두 번째입니다. 이것은 실행시간의 '성장률'이라고 부릅니다. 이 부분은 직관적으로 이해하기 어려우니 예를 통해 알아보겠습니다.
실행시간의 성장률이란?
입력값 크기가 n인 알고리즘이 6n2+100n+300이라는 명령을 받는다고칩니다. n값이 커지기 시작하면 6(n제곱)은 나머지 항목인 100n+300보다 커집니다. 아래 차트를 보면 n값이 0부터 100일 때의 6n2+100n+300의 값을 볼 수 있습니다.
이 차트를 통해, 100n+300을 빼고 주어진 알고리즘 식을 생각하면 실행 시간은 계수인 6을 빼고 n제곱으로 기하급수적으로 커지는 것을 볼 수 있습니다. 여기서 계수는 중요하지 않습니다. 아래의 차트에서 확인 할 수 있습니다.
상수의 변화에 따른 성장률을 비교하기 위해 0.6n제곱+1000n+3000d의 차트를 확인해보겠습니다. 계수와 나머지 상수는 달라졌지만 첫번째 차트와 마찬가지로 어느 기점에 교차점이 존재하고 n제곱은 기하급수적으로 커집니다.
점근적 표기법이란?
위에서 본 식에서 실행시간을 판단하기에 가장 중요한 항은 n제곱입니다. 이렇게 중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어집니다. 그리고 알고리즘 실행 시간에서 중요한 부분인 성장률에 집중할 수있습니다.
이러한 방식이 바로 '점근적 표기법'입니다. 그럼 점근적 표기법에는 어떤 형태가 있을까요? 세 가지의 형태가 있습니다.
바로 big-세타, big-O, big-오메가 표기법입니다.
다음 글에서 더 알아보겠습니다.