[Algorithm] 빅오분석법

빅 오분석(표현)법은 알고리즘의 성능이나 복잡도를 설명하는데 일반적으로 사용하는 표현 방법입니다.

빅 오 분석법에서는 입력 겂의 크개(개수)를 n개라고 가정하고, 이  n개의 입력된 값을 몇번이나 확인해봐야하는 지를 n의 식으로 표현한 것입니다. 즉, 동작하기 위해 필요한 연산횟수를 나타낸다고 생각하면 됩니다.

그리고, n이 무한대로 올라가면 n이나 n+2 나 크게 차이가 나지 않기 때문에 2와 같은 상수항은 그냥 무시해도 무방합니다.

빅 오 분석법을 적용하는 방법

1, 입력값이 무엇인지 확인 하고 어떤 것을 n으로 놓아야 할지 결정한다.

2. 알고리즘에서 수행해야할 연산 횟수를 n의 식으로 표현한다.

3. 차수가 제일 높은 항만 남긴다.

4. 모든 상수 인수를 없앤다.

어떤 알고리즘이 가장 빠른가?

가장 빠른 것은 O(1) 알고리즘으로, 보통 상수 실행시간(constant running time) 이라고 부른다. 입력의 개수와 무관하게 항상 일정한 시간안에 실행이 완료된다.

O(log n) : 실행 시간이 입력크기의 로그에 비례해서 늘어나는 알고리즘. (이진탐색)

O(n) : 실행시간에 입력 크기에 바로 비례하는 알고리즘을 선형 알고리즘이라고 부른다. (단순탐색)

O(n log n) : 초선형 알고리즘이라고 부르며, 속도가 선형알고리즘과 다항식 알고리즘의 중간정도. (퀵정렬)

O(n^c) : 입력 크기가 늘어나면 실행 시간이 빠르게 늘어나며, 다항식 알고리즘이라고 부른다. (선택정렬)

O (C^n) : 다항식 알고리즘 보다도 실행속도가 빠르게 느려지며, 지수 알고리즘이라고 부른다. 

O(n!) : 가장 느린 알고리즘으로, n이 작아도 금방 거의 쓰기 힘든 수준으로 느려지며 팩토리얼 알고리즘이라고 부른다. (외판원 문제)

아래는 종이에 네모칸의 수만큼 네모칸을 그린다고 했을 때 각 알고리즘의 속도를 나타낸 것입니다.

※ Hello Coding 그림으로 개념을 이해하는 알고리즘 책자의 그림을 발췌했습니다.