[자료구조] 1.2 알고리즘의 성능분석 방법 (1)

알고리즘의 성능분석 방법 (1)

기본 배경지식 : 지수와 로그

x축 : 데이터의 수
y축 : 연산의 횟수

시간복잡도와 공간복잡도

• 알고리즘의 수행시간을 분석하는 방식
  
• 시간복잡도(time complexity)는 알고리즘 수행 시간이 얼마나 걸리는지
  
• 공간복잡도(space complexity)는 메모리 공간이 얼마나 사용되는지

중요성

• 시간복잡도 > 공간복잡도
  
• 시간복잡도가 데이터 수에 대한 연산의 횟수를 판단하기 더 쉽다.

시간복잡도

평가 방법

• 중심이 되는 연산을 기준으로 횟수를 세어서 평가
  
• 함수 T(n) : 데이터 수에 대한 연산의 횟수

수행시간 비교

• 데이터 수가 적으면 수행 속도에 큰 의미가 없다.
  
• 데이터 수의 변화에 따른 수행 속도의 변화 정도로 비교한다
  

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의