알고리즘의 성능
1.
정확성 : 정확하게 동작하는가?
2.
작업량 : 얼마나 적은 연산을 수행하는가?
3.
메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
4.
단순성 : 얼마나 단순한가?
5.
최적성 : 더 이상 개선할 여지가 없을 만큼 최적화 되어 있는가?
알고리즘 수행 시간의 분석
알고리즘 수행시간이란 컴퓨터의 성능에 관계 없이 명확하게 정의될 수 있어야 하며, 필요한 경우 이미 알려진 수행 시간을 바탕으로 입력 데이터의 크기의 변화에 대한 수행시간의 변화를 예측할 수 있어야 한다.
점근 표기법(Asymptotic Notation)
알고리즘 수행 시간을 대략적으로 나타내는 방법
1.
Big O 표기법
•
알고리즘이 최악의 경우의 성능, 즉 수행 시간의 상한을 나타낼 때 사용.
•
빅오 표기법으로 표현된 성능은 어떤 최악의 상황에서도 그 성능을 보장한다는 의미
2.
Big Omega 표기법
•
알고리즘의 최선의 경우, 즉 수행 시간의 하한을 나타내는 방법
•
아무리 좋은 케이스라도 그 성능 이상을 낼 수 없음.
3.
Big Theta 표기법
•
처리해야 하는 수행 시간의 상한과 하한을 동시에 나타내는 표기법
Big O 표기법
•
해당 알고리즘이 최악의 경우에도 일정한 상수 시간에 종료된다는 것을 의미
•
해시 테이블
•
최악의 경우에도 입력 값 n이 증가하는 속도보다 수행 시간이 증가하는 속도가 느린 알고리즘의 성능을 나타낸다.
•
이러한 성능을 가진 알고리즘은 n이 10일 때 수행시간이 3.32 이고 n이 10000이 됐을 때도 여전히 13.29에 불과하다.
•
입력이 1000배가 늘어나도 수행시간은 고작 4배 정도 늘어난다.
•
이진 탐색
•
최악의 경우 입력 값 n 만큼의 수행 시간을 요구하는 성능.
•
입력 값 n 이 증가하는 속도만큼 수행 시간도 같은 속도로 증가한다.
•
순차 탐색
•
로그 함수가 사용되기는 했지만, 비교할 수 없을 정도로 수행시간이 길다.
•
병합 정렬, 퀵 정렬
•
최약의 경우 입력값 n에 대한 제곱의 수행시간이 늘어나는 성능
•
똑같이 n회 만큼 반복하도록 되어 있는 for 문이 2개 중첩되어 있을 경우
•
버블 정렬, 삽입 정렬
•
최악의 경우 입력값 n에 대한 세제곱의 수행시간이 늘어나는 성능
•
행렬 곱셉
•
입력값 n에 대해 최대 2의 n제곱 만큼 수행시간이 증가하는 경우
•
n이 10일 경우 수행 시간은 1024
