왜 $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $?

Question

$ \ omega (f) $ 은 F로 기능 세트를 낮은 바운드로 표시합니다. 왜 $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $ ?

1. 왼쪽의 기능을 전체 세트와 비교할 수 있습니까?나는 일반적으로 함수가 집합의 요소 인 것입니다. 즉 $ g \ in \ omega (f) $ g \ in \ omega (f) $ g \ span 클래스="수학 -컨테이너 "> $ g \ notin \ omega (f) $ .
$ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ omega (n \ sqrt {n} \ log_2n)$ 대신 왜 그것이 왜 그것이 사실인지 이해하지 못할 것입니다.왼쪽의 한계를 어떻게 평가합니까?

Answer 1

표기법 $ F=omega (g) $ f=omega (g) $ 및 $ f \ geq \ omega (g) $ < / span>은 동일합니다. 두 경우 모두, 그들은 큰 $ n $ 에 대해 긍정적 인 상수 $ c $ 이 존재한다는 것을 의미합니다. $ f (n) \ geq cg (n) $ .

다음과 같이 합계를 추정 할 수 있습니다. $$ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2 i \ geq \ sum_ {i= n / 2} ^ n \ sqrt {i} \ log_2 ^ 2 i \ geq \ sum_ {i= n / 2} ^ n \ sqrt {n / 2} \ log_2 ^ 2 (n / 2) \ geq \ frac {n} {2} \ cdot \ sqrt {n / 2} \ log_2 ^ 2 (n / 2). $$ 후자의 표현식은 $ \ omega (n ^ {3/2} \ log ^ 2 n) $ 보다 낫습니다.

일체형으로 합계를 추정 할 수도 있습니다. Wolfram 알파에 따르면, $$ \ int \ sqrt {x} \ log ^ 2 x \, dx=frac {2/2} (9 \ log ^ 2 x-12 \ log x + 8) + C. $$ $ \ sqrt {i} \ log_2 ^ 2 i $ 이 증가하고 있습니다. $$ \ int_0 ^ n \ sqrt {x} \ log ^ 2 x \, dx \ leq \ sum_ {i= 1} ^ n \ sqrt {i} \ log ^ 2 i \ leq \ int_1 ^ {n + 1} \ sqrt {x} \ log ^ 2 x \, dx, $$ 우리는 당신의 합계가 $ \ theta (n ^ {3/2} \ log ^ 2 n) $