对于这个关系式:
T(n) = T(n-1) + T(n/2) + n
我可以先解决项 (T(n-1) + n),得到 O(n^2),然后再解决项 T(n/2) + O(n^2) 吗?
根据主定理,这同样会得到 O(n^2) 吗?还是说这种方法是错误的?
对于这个关系式:
T(n) = T(n-1) + T(n/2) + n
我可以先解决项 (T(n-1) + n),得到 O(n^2),然后再解决项 T(n/2) + O(n^2) 吗?
根据主定理,这同样会得到 O(n^2) 吗?还是说这种方法是错误的?
我不认为你的方法在一般情况下是正确的。当你舍弃T(n/2)项来计算T(n-1)项的复杂度时,你最终低估了T(n-1)项的大小。
这里给出一个具体反例:
T(n) = T(n-1) + T(n-2) + 1
对于这个问题,您的技术可能会得出T(n) = O(n^2),但实际复杂度是指数级别的。