알고리즘 - 알고리즘의 기초(빅오표기법)

효율적인 알고리즘이란

계산량 고려하기

• 시간계산량 --> 시간이 얼마나 적게 걸리는가
• 공간계산량 --> 기억용량(메모리)을 얼마나 적게 사용하는가

시간계산량과 공간계산량 둘다 최소로 하는 것은 무리가 있다. 일반적으로 시간계산량이 적도록 구성하면 공간계산량이 증가하고, 반대도 마찬가지이다. 이는 마치 효과성과 효율성을 모두 잡겠다는, 그럴듯하지만 실현불가능한 목표와 같다. 

일반적으로 계산량 확인은 시간계산량을 고려하게 된다.

 

 

 

시간소요 줄이기

소요되는 시간은 cpu 성능에 따라 차이가 있을 수 있기 때문에 스텝의 개수로 판단한다

스텝은 수행되는 단계라고 보면 된다. 

 

시간계산량은 계산에 걸리는 복잡한 정도를 따진다. 계산이 복잡해질수록 단계도 많아지고 각 단계를 처리하는데 걸리는 시간도 증가하게 될 것이다. 시간을 줄이려면 1) 간단한 계산식 구성하기, 2) 계산할 단계 줄이기 와 같은 방식으로 접근할 수 있다.

 

 

 

O표기법(=오 표기법, 빅오 표기법)

빅오표기법은 데이터의 입력크기(n)에 따라 계산이 얼마나 늘어나는지 표현하는 방법이다. 크기가 작을수록 효율적인 방식이다. 표현되는 식은 최대실행 횟수이다. 가령 O(n)이라고 표시된 경우, 운이 좋다면 1번째에 찾을 수 있겠지만 최대 n번을 수행해야 단계를 넘어갈 수 있다는 의미이다. 2ⁿ은 아주 비효율적이다. 데이터가 10개라면 최대 1024번이나 수행해야한다.

기법	내용
O(n)	데이터의 개수가 n일때 스텝의 개수가 데이터의 개수에 비례한다
O(log n)	데이터의 개수가 n일때 스텝의 개수가 2를 스텝의 개수만큼 제곱한 값을 정수 배이다
O(n log n)	스텝의 개수가 n 로그에 비례한다
O(n²)	스텝의 개수가 데이터의 개수에 비례한다
O(2ⁿ)	스텝의 개수가 2의 n 제곱에 비례한다