解决复发关系$ 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 {n} $ 不是一个常量，它真的很难在这里应用树方法和主定理。任何提示吗？我的思想是，让 $ 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 ^ {-2}}，...，n ^ {2 ^ {-k}} $ 我们得到 $$ \ begin {align} 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）） \结束{align} $$

所以，我们得到 $$ t（n）\在o（n \ log_2（\ log_2（n）））$$