Question

求问下面时间复杂度的式子是怎么展开的？谁能帮我解释一下，这是属于数学的那个范畴？谢谢！

T(n) = 25T(n/5)+n^2
= 25(25T(n/25)+n^2/25)+n^2

Answer 1

这个式子的推导实际上是函数嵌套方面的知识。
首先针对这个函数：t(x)=25t(x/5)+t^2 ————式子一
实际上这个函数的本质是一层迭代关系，函数的原式应当是：t(5x)=25t(x)+(5x)^2
令x'=5x的时候就可以得到式子一了。
而第二行等式T(n) = 25(25T(n/25)+n^2/25)+n^2
实际上是令n=T(n)后进行迭代的出来的结果，换句话说就是把式子左端的T(n)整体作为变量n带入右边的式子计算得出。