T (n) = θ (n^2) = O (n^2) = Ω (n^2)가 다음과 같을 경우 T(n)=O(n)? T(n)=O(n^3)?만약 T (n) = θ (n^2)가 T (n) = 0 (n)이라면?
는, O (N4) 등 만이 O (N2), 또한 O (n2log의 N), O (N3)입니다하지 O (N) : 대답하지만 한 번 찾고
는 :
큰 O가 알고리즘은 주어진 식보다 더 많은 단계로 실행할 수단 (N^2)
예, 사실입니다.
다음
T(n) = O(n^k), T(n) = θ(n^2) 경우 여기서 T(n) = θ(n^2) 경우 T(n) = θ(n^2)로 T(n) != θ(n^3)가 n의 증가율을 의미 k<=2
주 성장 속도에 점근 동일 k>=2
T(n) = Ω(n^k)n^2.
반면에 T(n) = O(n^2) 인 경우 T(n) = O(n^3)은 T(n) = O(g(n))이 T (n)의 성장 속도가 g (n)의 성장 속도보다 작거나 같음을 의미하기 때문입니다. 따라서 T (n)의 성장률이 n^2의 성장률보다 작 으면 분명히 n^3보다 작을 것입니다.
무엇이 질문입니까? 제목 인 경우 대답은 '아니오'입니다. θ (n^2)는 알고리즘이 n^2 단계로 실행됨을 의미합니다. 더 적은, 더 이상. T (n) = O (n) 또는 T (n) = O (n^3)와 같으면 – Rahul
입니다. 이 답변 중 하나는 정확해야합니다 – Dziuba
T (n) = θ (n^2)이면 T (n) = O (n^3)입니다. 교과서를 참조하십시오. – Rahul