[알고리즘] 알고리즘 수행시간 유형 N

[알고리즘] 알고리즘 수행시간 유형 N

 

알고리즘 분석의 결과는 입력되는 자료의 수 N에 대하여 수행 시간을 함수 관계로 표현한 것이다.

 

1. 1

- 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘이다. 프로그램에서 대부분의 명령들은 한 번만 실행되거나, 단지 몇 번만 실행이 된다.

전체적인 프로그램이 이런 경우라면 실행 시간은 상수가 된다. 이 유형은 알고리즘의 설계시 도전해 볼 만한 것이다.

 

2. log N

- 만약 입력 자료의 수에 따라 실행 시간이 log N의 관계를 만족한다면 N이 증가함에 따라 실행 시간이 조금씩 늘어난다.

이 유형은 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형이다.

log의 성질상 밑(base)의 값에 따라 결과는 달라지지만 그렇게 크게 다르지는 않다. 예를 들어 N이 1000일 때 밑이 10이라면 결과는 3이 나오지만 밑이 2라면 약 10의 값을 가진다. 이 차이는 아주 작은 것이다. 

이 유형의 알고리즘도 굉장히 바람직한 실행시간을 갖는다.

예를 들어 성능이 좋은 검색 알고리즘은 대부분 log N의 수행 시간을 갖는다.

 

3. N

- 입력 자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우이다. 이는 입력 자료 각각에 일정 정도의 동일한 처리를 할 때 나타나는 경우이다. N이 두 배로 늘어나면 실행 시간도 두 배로 늘어난다.

이 유형도 납득할 만한 실행 시간을 갖는다.

 

4. N log N

- 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두 배로 늘어나면 실행 시간은 두 배보다 약간 더 많이 늘어난다.

예를들어 성능이 좋은 정렬 알고리즘의 실행시간은 N log N에 비례한다.

 

5. 

- 이 유형은 이중 루프 내에서 입력 자료를 처리하는 경우에 나타난다. N값이 큰 값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다. 그래서 이 유형의 알고리즘은 많은 양의 입력 자료에 대해서는 사용이 부적절하다.

N이 두 배로 늘어난다면 실행 시간은 네 배로 늘어난다.

 

6. 

- 이 유형은 앞의 유형과 비슷하게 입력 자료를 삼중 루프 내에서 처리하는 경우에 나타난다. N값이 커짐에 따라 실행 시간은 훨씬 더 커지게 된다. 역시 이 유형의 알고리즘은 다량의 입력 자료에 대해서는 부적절하며, 문제가 있는 알고리즘이 된다. N이 두 배로 늘어난다면 실행 시간은 여덟 배로 늘어난다.

 

7. 

- 입력 자료의 수가 늘어남에 따라 급격히 실행 시간이 늘어난다. 이 유형은 흔하지는 않지만 가끔씩 알고리즘을 처음 개발할 때 보인다. 하지만 이런 알고리즘은 대부분 더 좋은 성능의 알고리즘으로 개선된다. N이 두 배로 늘어난다면 실행 시간은 제곱으로 늘어난다.