[종만북] 책 내용 정리 2

프로그래밍 대회에서 배우는 알고리즘 문제해결전략 책 정리용

알고리즘 시간 복잡도 분석

• 알고리즘의 수행 시간을 지배하는것은 반복문이다.
• 선형 시간 알고리즘 -> O(n)
  • 선형 시간에 실행되는 알고리즘은 대개 가장 좋은 알고리즘인 경우가 많음
• 선형 이하 시간 알고리즘
  • 로그함수가 대표적. 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘들을 선형 이하 시간 알고리즘이라 부름
  • 이진탐색
• 지수 시간 알고리즘
  • N, N^2, N 거듭제곱들의 선형결합으로 이루어진 식들을 다항식이라고 부름
  • 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들을 다항 시간 알고리즘이라 부름
  • N이 하나 증가할때마다 걸리는 시간이 배로 증가하는 알고리즘들을 지수 시간 알고리즘이라고 함

시간 복잡도

• 점근적 시간 표기 : O 표기
  • 주어진 함수에서 가장 빨리 증가하는 항만을 남긴채 나머지를 다 버리는 표기법