자료구조와 알고리즘6

알고리즘의 복잡도

시간 복잡도

문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

공간 복잡도

문제의 크기와 이를 해결하는 데 걸리는 메모리 공간 사이의 관계

평균 시간 복잡도

임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

최악 시간 복잡도

가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

Big-O Notation (빅 오 표기법)

점근 표기법 (asymptotic notation)의 하나
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
(알고리즘의 복잡도를 표현할 때 흔히 쓰임)
O(logn), O(n)등으로 표기

입력의 크기가 n일때

O(logn) -입력의 크기의 로그에 비례하는 시간 소요
O(n) -입력의 크기에 비례하는 시간 소요

선형 시간 알고리즘 - O(n)

• 선형 탐색 알고리즘
  • Average case : O(n)
  • Worst case : O(n)

로그 시간 알고리즘 - O(logn)

• 이진 탐색 알고리즘

이차 시간 알고리즘 - O(n^2)

• 삽입 정렬 알고리즘
  • Best case : O(n)
  • Worst case : O(n^2)

보다 나은(낮은) 복잡도를 가지는 정렬 알고리즘

• 병합 정렬 알고리즘 - O(nlogn)
  • 정렬 문제에 대해 O(nlogn)보다 낮은 복잡도의 알고리즘은 존재 할 수없음