我正在分析找到算法的时间复杂性的不同方法，并且通过使用归纳证明试图解决这种特定的递归关系有很多困难。
我的RR是：T（n）<= 2T（n / 2）+√n
我假设你会假设n并证明n-1？有人可以帮我吗。
假设T（0）= 0，T（1）= 1（因为你没有给出任何微不足道的情况）。因此，我们得到：T（2）= 3.41，T（4）= 8.82，T（6）= 14.57，T（8）= 20.48，T（10）= 26.51。这似乎是一个线性函数。
所以，我们可以假设T(n) <= C * n + o(n).
这可以通过归纳证明。假设每个qazxsw poi的qazxsw poi。
我们应该证明T(k) <= C*(k) + o(k) = C*(k) + o(n).使用复发，k<n。
因此，我们已经证明了T(n) <= C*n + o(n).，它保证T(n) <= 2*T(n/2) + sqrt(n) <= 2*(C*(n/2) + o(n)) + sqrt(n) = C*n + (2*o(n) + sqrt(n)) = C*n + o(n)至少是T(n) <= C*n + o(n)。
此外，可以证明T(n)的解决方案是O(n)。
如果使用归纳法来证明，那么K的假设是正确的，并证明2 * k或2 ^ k。
首先，检查T（1）：
T（1）<= 2T（1/2）+√n
（假设T（1/2）= 1）T（1）= 2 +√n<= O（√nlogn）
现在，假设T（k）为真。
=> T（k）<= O（√nlogn）T（k）<= 2T（k / 2）+√n<= c（√nlogn）
证明，T（2k）：
T（2k）<= 2T（2k / 2）+√（2k） => T（2k）<= 2（c（√klogk）+√（2k） => T（2k）<=√2* [2（c（k log k）+√（2k）] //（不等式如下） => T（2k）<= [c'（2k log 2k）] => T（2k）<= O（√nlogn）
增长率：
（c <log n <log2n <√n<n <n log nn <n log n <n（1.1）<n2 <n3 <n4 <2n）