案例 d=log_b(a) 的主定理解
Master theorem solution for the case d=log_b(a)
来自 Dasgupta 的算法：如果分治算法的 运行 时间用递归 T(n)=aT(n/b)+O(n^d) 描述，那么它的解是：
T(n)=O(n^d) 如果 d>log_b(a)T(n)=O(n^log_b(a)) 如果 d<log_b(a)T(n)=O(n^d*log_2(n)) 如果 d=log_b(a)
其中每个子问题的大小在下一次递归调用中减少b，a是分支因子，O((n/b^k)^d)是在级别上划分和组合子问题的时间k 每个子问题。
情况 1 和情况 2 很简单 - 它们取自对递归树的每个级别完成的工作求和时形成的几何级数，即 a^k*O((n\b^k)^d)=O(n^d)*(a/b^d)^k.
情况 3 中的 log_2(n) 是从哪里来的？当d=log_b(a)时，比率a/b^d等于1，因此级数之和是n^d*log_b(a)，而不是n^d*log_2(n)
作为一个更简单的例子，首先注意O(log n)、O(log137 n)和O(log16 n) 意思相同。原因是，通过改变对数的基础公式，对于任何固定常数m，我们有
log_m n = log n / log m = (1 / log m) · log n = O(log n).
大定理假定 a、b 和 d 是常数。从对数基础公式的变化，我们有
从这个意义上说，O(nd logb n) = O(nd log n), 因为 b 在这里是一个常数。
注意，看到写成 O(nd log2 n 的东西是不寻常的，因为对数基这里无关紧要，只是有助于（已经隐藏的）常数因子。
来自 Dasgupta 的算法：如果分治算法的 运行 时间用递归 T(n)=aT(n/b)+O(n^d) 描述，那么它的解是：
T(n)=O(n^d)如果d>log_b(a)T(n)=O(n^log_b(a))如果d<log_b(a)T(n)=O(n^d*log_2(n))如果d=log_b(a)
其中每个子问题的大小在下一次递归调用中减少b，a是分支因子，O((n/b^k)^d)是在级别上划分和组合子问题的时间k 每个子问题。
情况 1 和情况 2 很简单 - 它们取自对递归树的每个级别完成的工作求和时形成的几何级数，即 a^k*O((n\b^k)^d)=O(n^d)*(a/b^d)^k.
情况 3 中的 log_2(n) 是从哪里来的？当d=log_b(a)时，比率a/b^d等于1，因此级数之和是n^d*log_b(a)，而不是n^d*log_2(n)
作为一个更简单的例子，首先注意O(log n)、O(log137 n)和O(log16 n) 意思相同。原因是，通过改变对数的基础公式，对于任何固定常数m，我们有
log_m n = log n / log m = (1 / log m) · log n = O(log n).
大定理假定 a、b 和 d 是常数。从对数基础公式的变化，我们有
从这个意义上说，O(nd logb n) = O(nd log n), 因为 b 在这里是一个常数。
注意，看到写成 O(nd log2 n 的东西是不寻常的，因为对数基这里无关紧要，只是有助于（已经隐藏的）常数因子。