我如何计算这个等式的成本？
How can I compute the cost of this equation?
我知道解是绿色的，但是我不知道怎么计算。
如果有人能解释我或只给我一个我能理解的link，我将不胜感激。
谢谢。
对于一般情况（n>1），递归是 n + T(n/2) + T(n/2)。
这可以简化为 2T(n/2) + n.
通过求解递归的Master Method，设a = 2, b = 2 and f(n) = O(n)。
根据定理，a的log(base b)是2的log(base 2)，显然是1。所以O(n^(log(base b) of a))是O(n ^(1)) 是 O(n).
主定理的情况 2 表示如果 f(n) 的复杂度等于 O(n^(log(base b) of a )), 那么整个循环的复杂度为 O(n^(log(base b) of a) * log(n)).
因此整体复杂度为 O(n^(log(base b) of a) * log(n)) 即 O(n * log(n)). 在处理复杂性时，我们可以交替使用 log(n) 和 lg(n)。所以选项C正确。
P.S。 here.
是关于如何应用 master 方法的一个很好的概述
我知道解是绿色的，但是我不知道怎么计算。
如果有人能解释我或只给我一个我能理解的link，我将不胜感激。
谢谢。
对于一般情况（n>1），递归是 n + T(n/2) + T(n/2)。 这可以简化为 2T(n/2) + n.
通过求解递归的Master Method，设a = 2, b = 2 and f(n) = O(n)。
根据定理，a的log(base b)是2的log(base 2)，显然是1。所以O(n^(log(base b) of a))是O(n ^(1)) 是 O(n).
主定理的情况 2 表示如果 f(n) 的复杂度等于 O(n^(log(base b) of a )), 那么整个循环的复杂度为 O(n^(log(base b) of a) * log(n)).
因此整体复杂度为 O(n^(log(base b) of a) * log(n)) 即 O(n * log(n)). 在处理复杂性时，我们可以交替使用 log(n) 和 lg(n)。所以选项C正确。
P.S。 here.
是关于如何应用 master 方法的一个很好的概述