재발 관계 $ 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 {정렬} 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 {정렬} $$

$$ t (n) \ in o (n \ log_2 (\ log_2 (n))) $$