반응형
알고리즘
-
점근적 표기법알고리즘 2021. 5. 12. 00:28
쉽게 배우는 알고리즘(문병로) p.39~ 뇌를 자극하는 알고리즘(박상현) p.471~ 점근적 표기법(Asymptotic Notation) : 알고리즘의 수행 시간을 대략적으로 나타내는 방법. → 최고차항만 남긴 후 계수 제거 Θ($f(n)$) : 최고차항의 차수가 $f(n)$과 일치하는 함수의 집합 $3n^2+2n$ = Θ($n^2$) $n^2+\sqrt{n}$ = Θ($n^2$) 버블 정렬 : Θ($n^2$), 병합 정렬 : Θ($n$log$n$) O($f(n)$) : 최고차항의 차수가 $f(n)$과 일치하거나 더 작은 함수의 집합. 함수의 점근적 상한 → 어떤 최악의 상황에서도 이 성능 보장 $3n^2+2n$ = O($n^2$) $5n$ = O($n^2$) → $5n$의 증가율이 $n^2$의 증가율보..