목록차수 주요 성질 (1)

코젤브

알고리즘 차수 표기법

- Big O 표기법 = worst와 비슷 : 점근적 상한 : 궁극적으로 이것보단 좋다(=기울기가 같거나 낮다) - Ω 표기법 : 점근적 하한 : 아무리 좋아도 이것보다 좋아질 수 없다(=기울기가 높다) - Θ 표기법 : 점근적 협소 : 차수가 같다(=기울기가 같다) - Small o 표기법 : 차수가 작다(=기울기가 낮다) (같을 수 없다) - 차수의 주요 성질 g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n)) g(n) ∈ Θ(f(n)) f(n) ∈ Θ(g(n)) 로그 복잡도 함수는 모두 같은 카테고리 => Θ(lg n) 지수 복잡도 함수는 모두 같은 카테고리 X n! 는 어떤 지수 복잡도 함수보다 나쁨 좋은 것부터 나열 n c ≤ 0, d > 0 일 때, g(n) ∈ O(f (n)), 그리고 h(..
컴공의 일상/알고리즘 2022. 5. 5. 02:58
이전 Prev 1 Next 다음