Wiederholungsrecurrence Relation $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $

Question

Angesichts der Bedingung: $ t (o (1))= o (1) $ und $ t (n) \ leq \ sqrt {n} t (\ sqrt {n}) + n $ .Ich muss diese Rezidivbeziehung lösen.Der schwierigste Teil für mich ist die Anzahl der Subproblems $ \ sqrt {n} $ ist nicht ständig, es ist wirklich schwierig, die Baummethode und den Master-Satz hier anzuwenden.Irgendein Hinweis?Mein Gedanke ist, dass $ c=sqrt {n} $ so, dass $ c ^ 2= n $ Also haben wir $ t (c ^ 2) \ leq ct (c) + c ^ 2 $ aber ich sehe nicht gut aus.

Answer 1

let $ k= k (n) $ Sei die kleinste positive Ganzzahl, so dass $ n ^ {2 ^ {-k}} <2 $ .Äquivalent $ k $ ist die kleinste positive ganze Zahl, so dass $ k> \ log_2 (\ \ log_2 (n)) $ .So, $$ K=lceil \ log_2 (\ log_2 (n)) \ RCEIL $$ Verwenden Sie wiederholt die Ungleichung mit $ n, n ^ {2 ^ {- 1}}, n ^ {2 ^ {- 2}}, ..., n ^ {2 ^ {-k}} $ wir bekommen $$ \ begin {richten} 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)) \ end {richten} $$

Also erhalten wir diesen $$ t (n) \ in O (n \ log_2 (\ \ \ \ \ log_2 (n))) $$