시간복잡도

조준형·2023년 3월 10일
0

알고리즘

목록 보기
2/7

알고리즘의 분석

알고리즘의 자원 사용량을 분석

자원이란?
실행 시간, 메모리, 저장장치, 통신 등

실행시간의 분석에 대해서 다룸

시간복잡도

실행 시간은 실행 환경에 따라 달라짐
-> 하드웨어, 운영체제, 언어, 컴파일러 등

실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트

연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현

  • bubble sort와 같은 경우에 입력 데이터 개수에 따라서 연산의 실행 횟수가 달라짐 -> n개가 있으면 n^2번 일수도 있고 2n번 일수도 있고 2n+3번 일수도 있음

데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
-> 최악의 경우 시간복잡도: 검색 알고리즘에서 첫번째에 바로 검색 성공할 수도 있고 더 늦게 성공할 수도 있음
-> 평균 시간복잡도: 간단한 케이스에서는 평균 시간복잡도를 사용하지만 복잡한 케이스에서는 보통 최악의 경우 시간복잡도를 사용

점근적 분석

점근적 표기법을 사용

  • 데이터의 개수 n -> ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법
  • Θ-표기, O-표기 등을 사용

유일한 분석법도 아니고 가장 좋은 분석법도 아님

  • 다만 (상대적으로) 가장 간단하며
  • 알고리즘의 실행환경에 비의존적임
  • 그래서 가장 광범위하게 사용됨
profile
코린이

0개의 댓글