使用迭代方法解决此递归关系的步骤是什么？
What are the steps to solve this recurrence relation using iteration method?
我对分析算法的时间复杂度比较陌生，无可救药地卡在了这个问题上。
T(n) = 2T(n/2) + Θ(n) ; n>1
T(1) = a
我了解到使用大师的方法可以轻松解决此问题，但是我想知道如何使用迭代方法执行此分析。
为简单起见，将 theta(n) 替换为 n。 （做题要彻底，得把theta(n)的定义展开出来，得到这个词的上下界，运行和下面一样的分析——这种做的很少见在实践中）。
现在假设 n 是 2 的幂：
T(n) = 2T(n/2) + n
= 4T(n/4) + n + n
= 8T(n/8) + n + n + n
= ...
= 2^kT(n/2^k) + kn
最终，n/2^k 为 1，此时 k 为 log_2(n)。
所以T(n) = nT(1) + log_2(n)*n
这个对n2的幂有效，但是可以注意如果n1是小于等于n的2的最大幂，而n2是大于或等于n的2的最小次方，那么T(n1) <= T(n) <= T(n2)，可以结合n1 >= n/2，n2 <= 2n的事实得到theta( n log n) 所有 n 的边界。
你最常看到的计算或工作与上面相同，但没有说明n必须是2的幂，并且完全忽略了四舍五入的细节。 Sedgewick 是一位严格研究这些细节的作者，例如，当他计算在长度为 n 的数组的合并排序中执行的比较的确切数量时。
我对分析算法的时间复杂度比较陌生，无可救药地卡在了这个问题上。
T(n) = 2T(n/2) + Θ(n) ; n>1
T(1) = a
我了解到使用大师的方法可以轻松解决此问题，但是我想知道如何使用迭代方法执行此分析。
为简单起见，将 theta(n) 替换为 n。 （做题要彻底，得把theta(n)的定义展开出来，得到这个词的上下界，运行和下面一样的分析——这种做的很少见在实践中）。
现在假设 n 是 2 的幂：
T(n) = 2T(n/2) + n
= 4T(n/4) + n + n
= 8T(n/8) + n + n + n
= ...
= 2^kT(n/2^k) + kn
最终，n/2^k 为 1，此时 k 为 log_2(n)。
所以T(n) = nT(1) + log_2(n)*n
这个对n2的幂有效，但是可以注意如果n1是小于等于n的2的最大幂，而n2是大于或等于n的2的最小次方，那么T(n1) <= T(n) <= T(n2)，可以结合n1 >= n/2，n2 <= 2n的事实得到theta( n log n) 所有 n 的边界。
你最常看到的计算或工作与上面相同，但没有说明n必须是2的幂，并且完全忽略了四舍五入的细节。 Sedgewick 是一位严格研究这些细节的作者，例如，当他计算在长度为 n 的数组的合并排序中执行的比较的确切数量时。