[알고리즘]알고리즘 성능에 대하여

알고리즘의 성능

성능을 측정 할 수 있는 기준 5가지

1. 정확성 : 정확하게 동작하는가

입력에 대해서 몇 번을 수행해도 동일한 결과를 정확하게 출력하는가

2. 작업량 : 얼마나 적은 연산을 수행하는가

수행해야 하는 작업의 양이 얼마나 되는가

버블 정렬은 정렬을 수행하기 위해 얼마나 작업이 필요한가

3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가

작업을 수행하는데 얼마의 메모리가 필요하는가

4. 단순성 : 얼마나 단순한가

컴퓨터가 이해하기에 복잡하지 않고 단순한가

5. 최적성 : 더 이상 개선 할 여지가 없을만큼 최적화 되어 있는가

컴퓨터가 이해하는데 최적화 되어 있는가

알고리즘 수행 시간 분석

알고리즘의 시작 시간부터 종료 시간까지의 시간 분석은 수행 시간을 측정 할 수 없습니다.

1. CPU의 성능에 따라 시간이 달라집니다.

2. 입력 매개 변수의 수행 시간을 측정 할 수 없습니다.

정확한 시간을 측정 할 수는 없지만 작업의 양을 통해 추정 할 수 있습니다.

 알고리즘은 최악의 경우를 산정하는 경우가 많습니다.

 프로그램은 잘 돌아갈 때는 문제가 안되지만 문제는 항상 안돌아가거나 느려서입니다.

1. 최악의 경우 : Big(O) -> 빅오

가장 안좋은 경우에 걸리는 수행 시간을 뜻합니다.

택배가 7일 안에 온다고 했을 때 아무리 늦어도 7일날 오는 경우입니다.

2. 최선의 경우 : Ω -> 오메가

가장 좋은 경우에 걸리는 수행 시간을 뜻합니다.

택배가 7일 안에 온다고 했을 때 아무리 빨라도 1일날 오는 경우입니다.

3. 평균의 경우 : Θ -> 세타

최악과 최선 안에서 걸리는 수행 시간을 뜻합니다.

택배가 7일 안에 온다고 했을때 이러든 저러든 1-7일 안에 오는 경우입니다.

점근 표기법

Big(O) : 빅오 

최고차 항만 작성

ex) 2n^3+10n -> O(n^3)

표기법	설명	알고리즘
O(1)	일정한 상수 시간만큼 수행 시간이 걸리는 알고리즘	해시 테이블
O(log2^n)	입력 n이 증가하는 속도보다 수행 시간이 증가하는 속도가 느린 알고리즘	이진 탐색
O(n)	입력 값 n만큼 수행 시간이 증가하는 알고리즘	순차 탐색
O(n log n)	입력 값 n만큼과 log n을 더한 만큼 수행 시간이 증가하는 알고리즘	병합 정렬, 삽입 정렬
O(n^2)	입력 값 n의 제곱만큼 수행 시간이 증가하는 알고리즘	버블 정렬, 삽입 정렬
O(n^3)	입력 값 n의 세제곱만큼 수행 시간이 증가하는 알고리즘	행렬 곱셈
O(2^n)	입력 값 n의 2의 n제곱만큼 수행 시간이 증가하는 알고리즘

성능분석

참고