'시간복잡도' 태그의 글 목록

점근적 표기법 점근적 표기법에는 크게 O, Ω, Θ 각 빅-오, 빅-오메가, 빅-세타라고 부릅니다. 다음 다항식을 점근적 표기법으로 분류해보겠습니다. 예시 다항식 : n^3+n^2+n−1 O(빅-오)에서는 가장 높은 차수보다 같거나 높은 식을 뜻합니다. O(n^3), O (n^6) O(n^100) 모두 표현 가능하지만, 타이트하게 O(n^3)으로 라고 결정합니다. Ω(빅-오메가) 가장 높은 차수보다 같거나 낮은 식을 뜻합니다. Ω(n^3), Ω(n), Ω(logn) 모두 표현할수 있습니다. Θ(빅-세타) 는 최고차항을 뜻합니다. 가장 높은 차수는 n3 이므로 Θ(n3)이 됩니다. 대입과 조건문의 시간복잡도 코드의 실행 횟수를 점근적 표기법으로 추상적으로 표현할 수 있는데 이것을 시간복잡도라고 부릅니다. ..