لماذا $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $؟

Question

حيث $ \ Omega (F) $ يدل على مجموعة الوظائف مع F as المنخفضة، لماذا $ \sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ geq \ omega (n \ sqrt {n} \ log_2n) $ ؟

1. كيف يمكن مقارنة وظيفة على اليسار بمجموعة كاملة؟اعتقدت عادة وظيفة هي عنصر المجموعة، أي $ g \ in \ omega (f) $ أو أنها ليست كذلك، أي $ g \ notin \ omega (f) $ .
2. إذا كان الأمر كذلك $ \ sum_ {i= 0} ^ n \ sqrt {i} \ log_2 ^ 2i \ in \ omega (n \ sqrt {n} \ log_2n)$ بدلا من ذلك، ما زلت لا أفهم لماذا صحيح.كيف تقيم الحد الأقصى للجانب الأيسر؟

Answer 1

الرموز $ f=omega (g) $ و $ f \ geq \ omega (g) $ متطابقة. في كلتا الحالتين، تعني أن هناك موجودة حاوية إيجابية $ c $ مثل $ n $ ، $ 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} {3/2} \ سجل ^ 2 n) $ ، وهو أفضل مما تدعيه.

يمكنك أيضا تقدير المبلغ من خلال جزء لا يتجزأ. وفقا ل Wolfram Alpha، $$ \ Int \ sqrt {x} \ Log ^ 2 x \، dx=frac {2} {2} x ^ {3/2} (9 \ log ^ 2 x - 12 \ Log X + 8) + C. $ منذ $ \ sqrt {i} \ log_2 ^ 2 $ $ متزايد، لدينا $$ \ 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) $ .