[자료구조와 알고리즘] 알고리즘의 분석

경험적 분석과 수학적 분석

• 분석은 알고리즘을 선택하기 위한 방법
• 자원을 어떻게 소모하느냐가 중요. 시간 VS 자원
• 경험적 분석(Empirical Analysis)
  • 실제 코드를 작성 후 실행하여 시간 측정
  • 데이터 수를 다르게 하여 함수 관계 유추 (테스트케이스)
• 수학적 분석(Mathematical Analysis)

최악의 경우와 최선의 경우 (경험적 알고리즘)

• Worst Case
• 가장 많은 시간과 자원을 필요로 하는 경우
• Best Case
• 가장 적은 시간과 자원만이 소요되는 경우
• Average Case
• 개념 모호

알고리즘 분석 예 (수학적 알고리즘)

• For문을 수학적으로 돌리는 예시 

  

알고리즘의 유형

상수

• 입력자료수와 상관없이 일정한 실행시간
• ex 해쉬 검색 알고리즘 등

log N

• Divide&Conquer 방법 사용 시
• 이진검색, 이진트리검색 등

N

• Scan방법 사용 시(자료를 쭉 스캔해서 검사)
• 선형검색 등

N log N

• Divide&Conquer&Merge 방법 사용 시
• 병합정렬 등

N^2

• 이중 루프(For문)
• 삽입정렬, 선택정렬 등

N^3

• 삼중 루프(행렬의 곱셈 등)

알고리즘 성능 표기법 (Big-O)

알고리즘 성능을 수학적으로 표기해주는 표기법이다.

알고리즘의 실행시간보다는 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표이므로 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거한다.

즉, 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.

시간 복잡도

시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.

따라서 시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한 것이라고 볼 수 있다.

컴퓨터 성능에 따라 실행시간은 달라질 수 있으므로 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구하게 된다.

오메가 표기법, 세타 표기법도 있음