-
추상 자료형
자료의 형태와 관계된 연산을 수학적으로 정의한 것을 말하며 구체적인 구현을 포함하지 않는다.
이러한 추상화를 통해 알고리즘 정의를 단순화할 수 있다.
자료 연산 추상화 추상 자료형 알고리즘 정의 구체화 자료형 프로그램 구현 알고리즘의 표현 방법
- 자연어 사람이 사용하는 언어를 사용한다. 일관성과 명확성을 유지하기 어렵다.
- 순서도 순서도의 작성 규칙에 따라 도식화한다. 복잡한 알고리즘의 표현이 어렵다.
- 프로그래밍 언어 특정 프로그래밍 언어로 작성하여 추가적인 구체화 작업이 필요하지 않다. 해당 언어를 모르는 사람이 이해하기 어려울 수 있으며 다른 언어에서 사용이 필요한 경우 다시 번역하여 변환하는 추가 작업이 필요하다.
- 가상 코드 프로그래밍 언어의 형태를 갖춘 추상화된 가상의 언어로 표현한다.
알고리즘 성능 분석 방법
- 공간 복잡도 알고리즘을 실행한 뒤 완료할 때까지 필요한 총 저장공간을 의미한다. 현재는 메모리의 제약이 크지 않기 때문에 주요한 관심사가 되지 않는다.
- 시간 복잡도 알고리즘을 실행한 뒤 완료할 때까지 걸리는 시간을 의미한다. 실제 실행 시간은 기기의 사양에 따라 바뀔 수 있으므로 명령어의 실행 빈도수를 통해 계산한다.
- 빅 오 표기법 시간 복잡도를 단순화 하기 위해 가장 큰 단위를 제외한 나머지를 버려 표기하는 방식이다.
시간 복잡도의 계산 결과 → 빅 오 표기법
n² + 8n + 3 → O(n²)
nLogn + n + 1 → O(nLogn)Logn + 17n → O(n)
실행 시간 함수에서 n값의 변화 비교
logn n nlogn n² n³ 2ⁿ n! 2 1 2 2 4 8 4 2 3 1.6 3 4.8 9 27 8 6 4 2 4 8 16 64 16 24 5 2.3 5 11.6 25 125 32 120 º º º º º º º º 100 .6 100 664.4 100 1,000,000 1.267506002e+30 9.332615444e+157 101 6.7 101 672.5 10201 1,030,301 2.5354012005e+30 9.4259477598e+159 102 6.7 102 680.6 10404 1,061,208 5.0706024009e+30 9.614466715e+161 º º º º º º º º 1000 10 1,000 9,965.8 1,000,000 1,000,000,000 1.0715086072e+301 n=169, 4.269068009e+304 ※ 소수점 1자리에서 반올림
실행 시간 함수 그래프 표현 더보기참고문헌