알고리즘 효율성 분석

알고리즘 효율성 분석

• 시간의 효율성
• 공간의 효율성
• 코드의 효율성

시간의 효율성

• 주어진 조건에서 문제를 해결하기 위해 가능한 한 빠른 시간안에 가장 효율적으로 해결책을 찾는 것
• 시간복잡도
  • 시간복잡도는 알고리즘에서 사용된 입력크기와 단위연산이 몇 번 수행되는지 함수로 표현

공간의 효율성

• 컴퓨터의 메모리를 얼마나 사용하는지에 따라 효율성을 결정
• 공간복잡도

코드의 효율성

• 개발자 입장
  • 변수명과 주석 등 이해하기 쉽도록 작성되어 코드의 가독성이 좋고 유지보수가 용이하도록 모듈화를 잘해 놓은 코드
• 하드웨어 입장
  • 컴퓨터와 하드웨어의 입장에서 작성된 코드

알고리즘 분석 방법

• Every case analysis
  • 입력크기에 종속
  • 입력값과는 무관함
• Worst case analysis
  • 입력크기와 입력값 모두에 종속
  • 단위연산이 수행 횟수가 최대인 경우
• Best case analysis
  • 입력크기와 입력값 모두에 종속
  • 단위연산 수행 횟수가 최소인 경우
• Average case analysis
  • 입력크기와 입력값 모두에 종속
  • 모든 입력에 대해서 단위연산이 수행되는 기대치(평균)

-----------------------------------------------------------------------

KOCW 알고리즘(이충기 교수님)