我有递归关系：T(n) = c*T (n/3) + (c/2)*n
对于任何C
设t（n）>=n^1.5为代换法的一个猜想。
最佳答案
假设T(n) <= n^1.5是正确的路径这样我们就可以：T(n) <= 6 ( n^1.5 / 3^1.5 ) + 3n=(6 / 3^1.5)* n^1.5 + 3n。6/3^1.5是5.1…但现在让我们称之为a。所以我们有：a*n^1.5 + 3n。
我们需要证明对于n0>nc*n^1.5 > a*n^1.5 + 3n存在c>0第一个设除以n：c*n^0.5 > a*n^0.5 + 3，得到：(c-a)*n^0.5 > 3。
从这里可以清楚地看到，您可以选择任何c > a和n > 9，因此这将是正确的。
总结：我们将T(n)变大到T'(n) = (6/3^1.5)*n^1.5 + 3n并证明对于c > 6/3^1.5和n > 9来说T(n) < cg(n) where g(n) = n^1.5
关于algorithm - 问:按替代的递归关系，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52306570/