알고리즘 과목이 다루는 주된 내용
- 문제를 푸는 방법과 그 방법의 효율을 분석하는 것
컴퓨터 알고리즘
- 문제를 해결하거나 함수를 계산하기 위해 모호함이 없는 간단한 명령들로 구성된 일련의 순서적 단계를 의미함.
알고리즘이 만족해야할 조건
- 0개 이상의 입력
- 1개 이상의 출력
- 단순하고 모호하지 않은 단계
- 한정된 단계 후에는 반드시 종료
- 모든 명령은 수행 가능
성능 분석
-
공간 복잡도
- 실행에 필요한 저장 공간
- 동일 입력 / 출력 일 때, 저장 공간을 적게 사용하면 좋은 알고리즘
-
시간 복잡도
- 실행에 걸리는 시간
- 동일 입력 / 출력 일 때, 빠르면 좋은 알고리즘
-
공간 복잡도 보다 시간 복잡도가 중요
-
시간 복잡도 측정
- 시간을 직접 측정하면 컴퓨터 성능에 따라 차이가 발생함
- 실행되는 알고리즘의 연산 개수를 계산함. 컴퓨터 성능과 무관하기 때문