[Algorithm] 점근 성능 분석(Asymptotic Analysis)

점근 성능 분석(Asymptotic Analysis)이란? 실행시간과 입력값(Running Time & Input) 점근 성능에 대해서 자세히 알기 전에 실행시간과 입력값 사이의 관계에 대해서 알아봅시다.

알고리즘의 실행시간은 input에 영향을 받습니다. 예를 들면, 이미 정렬된 배열은 좀 더 쉽게 정렬할 수 있습니다.

알고리즘의 실행시간은 input의 크기에 영향을 받습니다. 예를 들면, 4개의 원소를 갖는 배열보다 10개의 원소를 갖는 배열이 정렬하는 데 더 오래 걸립니다.

일반적으로 이러한 input에 대한 실행시간의 상한선을 구해 최악의 경우에도 보장되는 성능을 구하는 것이 알고리즘 분석의 주 목적입니다. 길이가 n인 input에 대한 알고리즘의 실행시간을 T(n)이라고 표현합니다.

이러한 input에 영향받는 수행시간을 경우에 따라 3가지로 나눠서 분석합니다. 최악의 경우(Worst Case) - 알고리즘 분석을 한다고 할 때 반드시 분석해야 하는 경우로 어떠한 크기의 i...

요청 처리 중입니다...

[Algorithm] 점근 성능 분석(Asymptotic Analysis)

등록된 다른 글