[알고리즘] 시간 복잡도

logn < n < nlogn < n^2 < n^3 < 2^n < n!

분석

• 입력 크기에 따라, 단위 연산이 몇 번 수행되는지 결정하는 절차
• 사용하는 자료구조에 좌우되는 경우도 있다.
• 표현 척도
  • 단위 연산 : 비교 / 지정
  • 입력 크기 : 배열의 크기 / 리스트의 길이 / 행과 열의 크기 / 트리의 노트와 연결선의 수

분석 방법

• 최선의 경우 (Best-case) :
  • 단위 연산 수행 횟수가 최소인 경우
  • 잘 안 쓴다.
  • ex) 순차검색의 x가 제일 처음에 위치하면 T=1
• 최악의 경우 (Worst-case)
  • 단위 연산 수행 횟수가 최대인 경우
  • 대부분 최악의 경우로 구한다.
  • ex) 순차검색의 x가 제일 마지막에 위치하면 T=n
• 평균의 경우(Average-case)
  • (최선+최악)/2 로 계산
  • 최악의 경우보다 계산이 복잡
  • ex) 순차검색의 평균의 경우 T = (1+n)/2

어떤 분석이 가장 정확한가?

: 하나만 골라 정확하다고 할 수 없다.

단, 최선의 경우는 거의 쓰지 않고, 보통 최악의 경우로 많이 사용한다.