带 logn 的主定理
Master theorem with logn
这里是 problem。
我真的很困惑 c 等于 0.5 部分。实际上总的来说我很困惑 logn 怎么会变成 n^(0.5)。难道我不能让 c 等于 100 这意味着 100 < d 会导致使用不同的大小写吗？我在这里错过了什么？
你当然 可以 设置 c = 100 以便 n^c 是 log(n) 的（非常，非常）粗略的渐近上限，但这会给你一个可怕且绝对无用的运行时间估计 T(n)。
它告诉你的是：每个多项式函数 n^c 的增长速度都比对数快，无论 c 有多小，只要它保持正数。你可以取 c=0.0000000000001，一开始它似乎变得小得离谱，但在某个时候它会变得比 log(n) 大并且发散到无穷大的速度比 log(n) 快得多。因此，为了摆脱 n^2 log(n) 项并能够应用主定理的仅多项式版本，您可以通过增长足够慢的东西（但仍快于 log(n)).在此示例中，n^c 和 c=0.5 就足够了，但您也可以使用 c=10^{-10000} "just to make sure".
然后你应用 Master 定理，并为你的 T(n).
得到一个合理的（和锐利的）渐近上限
这里是 problem。
我真的很困惑 c 等于 0.5 部分。实际上总的来说我很困惑 logn 怎么会变成 n^(0.5)。难道我不能让 c 等于 100 这意味着 100 < d 会导致使用不同的大小写吗？我在这里错过了什么？
你当然 可以 设置 c = 100 以便 n^c 是 log(n) 的（非常，非常）粗略的渐近上限，但这会给你一个可怕且绝对无用的运行时间估计 T(n)。
它告诉你的是：每个多项式函数 n^c 的增长速度都比对数快，无论 c 有多小，只要它保持正数。你可以取 c=0.0000000000001，一开始它似乎变得小得离谱，但在某个时候它会变得比 log(n) 大并且发散到无穷大的速度比 log(n) 快得多。因此，为了摆脱 n^2 log(n) 项并能够应用主定理的仅多项式版本，您可以通过增长足够慢的东西（但仍快于 log(n)).在此示例中，n^c 和 c=0.5 就足够了，但您也可以使用 c=10^{-10000} "just to make sure".
然后你应用 Master 定理，并为你的 T(n).