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

Question

wobei $ \ omega (f) $ die Funktionen der Funktionen mit F als niedrigerer Grenze bezeichnet, warum ist $ \Sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omga (n \ sqrt {n} \ log_2n) $ ?

.
1. Wie kann die Funktion auf der linken Seite mit einem ganzen Satz verglichen werden?Ich dachte normalerweise, dass eine Funktion ein Element des Sets ist, dh $ g \ in \ omega (f) $ oder es ist nicht, dh $ g \ notin \ omega (f) $ .
2. Wenn es sagen würde, dass es $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ omga (n \ sqrt {n} \ log_2n)$ Stattdessen würde ich immer noch nicht verstehen, warum es wahr ist.Wie bewerten Sie das Limit der linken Seite?

Answer 1

Die Notationen $ F=Omega (G) $ und $ F \ GEQ \ OMEGA (G) $ < / span> sind identisch. In beiden Fällen bedeuten sie, dass es eine positive Konstante gibt, die $ C $ so besteht, dass für große $ n $ , $ F (n) \ geq cg (n) $ .

Sie können die Summe wie folgt abschätzen: $$ \ 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). $$ Der letztere Ausdruck ist $ \ omega (n ^ {3/2} \ log ^ 2 n) $ , was besser ist als das, was Sie behaupten.

Sie können die Summe auch von einem Integral abschätzen. Laut Wolfram Alpha, $$ \ int \ sqrt {x} \ \ sqrt {x} \ \ ^ 2 x \, dx=frac {2} {27} x ^ {3/2} (9 \ log ^ 2 x - 12 \ log x + 8) + C. $$ Da $ \ sqrt {i} \ \ \ sqrt {i} \ log_2 ^ 2 I $ zunimmt, haben wir $$ \ 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, $$ Von dem wir sehen, dass Ihre Summe $ \ theta (n ^ {3/2} \ log ^ 2 n) $ ist.