목록Java/쉽게 배우는 자료구조 (1)
Hyunebee
점근적 표기법
점근적 표기법 우리는 알고리즘의 복잡도를 점근적 표기법으로 표기한다. 대표적인 표기법으로 3가지가 있다. 빅오 -> 점근적 상한 세타 -> 점근적 동등 오메가 -> 점근적 하한 빅오표기법 만약 Ο(n^2)이라면 최고차항이 n^2을 넘지않는 집합을 말하는 것이다. 즉 n, n^2 + 3n + 2, nlogn등 모두 포함이 된다. 기껏해야 n^2이라는 뜻이다. 만약 nlogn을 Ο(n^2)으로 표현해도 틀린말은 아니지만 더욱 정확하게 Ο(nlogn)으로 쓰는것이 더욱 적절한 정답이다. 수학적 정의 O(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0, cg(n) ≥ f(n) } 쉽게 설명해서 말하자면 충분히 큰 n에 대해서 cg(n) ≥ f(n)을 만족하는 상수 c가 존재한다...
Java/쉽게 배우는 자료구조
2022. 3. 17. 12:36