by Jerry Sky
2020-03-09
T(n)=2T(n)+log2nT(n) = 2T(\sqrt{n}) + \log_2 nT(n)=2T(n)+log2n m=log2nm = \log_2 nm=log2n, n=2mn = 2^mn=2m, S(m)=T(2n)=T(n)S(m) = T(2^n) = T(n)S(m)=T(2n)=T(n) T(2m)=2⋅T(2n2)+mT(2^m) = 2\cdot T(2^{\frac{n}{2}}) + mT(2m)=2⋅T(22n)+m
S(n)=2⋅S(n2)+m=Θ(mlogm)S(n) = 2\cdot S(\frac{n}{2}) +m = \Theta(m\log m)S(n)=2⋅S(2n)+m=Θ(mlogm) - ta równość wynika z poprzednich metod
T(n)=S(m)=Θ(mlogm)=Θ((logn)⋅(loglogn)) T(n) = S(m) = \Theta(m\log m) =\Theta\big((\log n) \cdot (\log \log n)\big) T(n)=S(m)=Θ(mlogm)=Θ((logn)⋅(loglogn))