알고리즘의 효율성 분석 개요

• 알고리즘의 시간 복잡도와 공간 복잡도의 개념을 이해하고 그 차이점을 설명할 수 있다.
• 알고리즘에서 효율성의 개념을 이해하고, 주어진 코드 또는 알고리즘에 대하여 최선 의 경우와 최악의 경우, 평균의 경우에서 효율성을 분석할 수 있다.
• Big-Oh, Big-Omega, Theta 표기법을 이용하여 알고리즘의 시간 복잡도를 점근적으 로 표기하는 방법을 이해할 수 있다.
• 시간 복잡도의 점근적 표기법을 함수 그래프로 표현하고, 상한과 하한의 관계를 설명 할 수 있다.

알고리즘의 효율성을 표현하는 방법

알고리즘의 효율성

• 알고리즘의 수행 시간(시간 복잡도) 또는 알고리즘이 수행하는 동안 사용되는 메모리 크기(공간 복잡도)로 나타낼 수 있음
• 일반적으로 시간 복잡도가 주로 사용됨

시간 복잡도

• 시간 복잡도는 알고리즘이 실행되는 동안에 사용된 기본 연산의 횟수를 입력 크기에 대한 함수로 나타낸다.
• 여기서 기본 연산(Elementary Operation)이란 데이터 간 크기 비교, 데이터 읽기, 갱신, 숫자 계산 등과 같은 단순한 연산을 의미

시간 복잡도와 점근적 표기법