حل تكرار العلاقة $ T (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

إعطاء الشرط: $ t (o (1))= o (1) $ و $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $ .أحتاج إلى حل علاقة تكرار هذه.الجزء الأصعب بالنسبة لي هو عدد المشكلات الفرعية $ \ sqrt {} $ ليس ثابتا، من الصعب حقا تطبيق طريقة الشجرة ودرجة رئيسية هنا.أي تلميح؟فكرتي هي أن تجعل $ c=sqrt {n} $ مثل $ c ^ 2= n $ لذلك لدينا $ t (c ^ 2) \ leq ct (c) + c ^ 2 $ ولكن أنا لا تبدو جيدة.

Answer 1

دع $ k= k (n) $ يكون أصغر عدد صحيح موجب مثل $ n ^ ^ ^ ^ ^ ^ {2 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^-k}} <2 $ .معادل $ K $ هو أصغر عدد صحيح موجب مثل $ k> \ log_2 (\ log_2 (n)) $ .لذلك، $$ k=lceil \ log_2 (\ log_2 (n)) \ rceil $$ باستخدام عدم المساواة مرارا وتكرارا مع $ n، n ^ {2 ^ {- 1}}، n ^ {2 ^}، ...، n ^ {2 ^ {-k}} $ نحصل عليه $$ \ ابدأ {محاذاة} T (n) & \ leq n ^ {1/2} t (n ^ {1/2}) + n \\ & \ leq n ^ {1/2 + 1/4} t (n ^ {1/4}) + 2n \\ & \ leq n ^ {1/2 + 1/4 + 1/8} T (n ^ {1/8}) + 3n \\ & ... \\ & \ leq n ^ {1/2 + 1/4 + ... + 1/2 ^ k} t (n ^ {2 ^ {- k}}) + kn \\ &= n ^ {1-2 ^ {- k}} o (1) + kn \\ & \ leq n ^ {1-1 / \ log_2 (n)} o (1) + n \ log_2 (\ log_2 (n)) \\ &=frac {n} {2} o (1) + n \ log_2 (\ log_2 (n)) \ نهاية {محاذاة}

لذلك، نحصل على هذا $$ T (n) \ in O (n \ log_2 (\ log_2 (n))) $