۰
subtitle
سلام.من این جوری حل میکنم:
طرفین رو در n ضرب میکردم و معادله این شکلی میشد:
nT(n)=√nT(√n)Log(n)
خب حالا nT(n)=F(n)
پس داریم:
F(n)=F(√n)Log(n)
حالا تغییر متغیر n=2m رو انجام میدیم پس داریم:
F(2m)=F(2m2)m
و داریم F(2m)=am
پس داریم:
am=a(m2)m
که داریم طبق قضیه اصلی F(n)=θ(m)=θ(Log(n))
و از طرفی داریم :F(n)=n.T(n)→T(n)=θ(Log(n)n)
طرفین رو در n ضرب میکردم و معادله این شکلی میشد:
nT(n)=√nT(√n)Log(n)
خب حالا nT(n)=F(n)
پس داریم:
F(n)=F(√n)Log(n)
حالا تغییر متغیر n=2m رو انجام میدیم پس داریم:
F(2m)=F(2m2)m
و داریم F(2m)=am
پس داریم:
am=a(m2)m
که داریم طبق قضیه اصلی F(n)=θ(m)=θ(Log(n))
و از طرفی داریم :F(n)=n.T(n)→T(n)=θ(Log(n)n)