问题标签 [master-theorem]

有人可以再澄清一下这个解决方案吗？

T(n) = 2T(n^1/2) + log n

解决方案：

令 k = log n，

T(n) = T(2^k)=2T(2^(k/2)) + k

代入方程 S(k) = T(2^k)

我们明白了

S(k)=2S(k/2) + k

现在，这个递推方程允许我们使用主定理，它指定

S(k) 是 O(k log k)。代回 T(n) 意味着 T(n) 是 O(log n log log n)

这是我要计算其运行时间的算法：

n 是正自然数的一部分，c0 和 c1 是常数。

这是java代码中的算法：

我正在寻找一种方法或解释示例。

我试图编写一个程序来使用前序序列构造一个二叉搜索树。我知道有很多解决方案：最小/最大算法、经典（或“明显”递归）甚至迭代而不是递归。

我尝试实现经典递归：前序遍历的第一个元素是根。然后我搜索所有小于根的元素。所有这些元素都将成为左子树的一部分，而其他值将成为右子树的一部分。我重复这一点，直到我构建所有子树。这是一种非常经典的方法。

这是我的代码：

我的问题是：这个算法的时间复杂度是多少？是 O(n^2) 还是 O(n * log(n) ) ？

我在stackoverflow中搜索了这里，但我发现了许多相互矛盾的答案。有时，有人说它是 O(n^2)，有时是 O(n*log(n))，我真的很困惑。

我们可以在这里应用主定理吗？如果是，“也许”我们可以考虑每次我们将树分成两个子树（相等部分），所以我们会有关系：（O（n）是在数组中搜索的复杂度）

T(n) = 1/2 * T(n/2) + O(n)

这会给我们带来O(n*log(n)). 但是，我认为这不是真的，我们不会将树分成相等的部分，因为我们在数组中搜索直到找到足够的元素，不是吗？

是否可以在这里应用主定理？

主定理可用于解决递归关系，如 T(n)= aT(n/b)+f(n).

那么，如果f(n)=O(n)或如果f(n)=cn两个值相同？我也可以使用主定理f(n)=cn吗？

我和我的朋友吵架，我们昨天考试了。我说不能，他说这是案例 1。可能他是对的，但我似乎不明白为什么。提前致谢。

假设我们有一个虚构的合并排序，其中合并操作的成本O(n^2)不是O(n). 然后根据主定理，我们有：

由于a < b^d，我们发现：

然而，直观地说，大 O 也是有道理的，T(n) = O(n^2 logn)因为每次递归都会对数字执行二次 ( n^2) 搜索。例如，在线性搜索的情况下，归并排序是O(n logn). 有谁知道为什么没有绑定O(n^2 logn)？这可能与每次递归时搜索减半的事实有关吗？

Master theorem的通用形式提到：

假设所有子问题的大小基本相同

Akra-Bazzi 方法适用于以下情况：

子问题的大小有很大不同

但是，实质性不同的标准是什么？例如，我有一个递归关系，如：

我仍然可以使用主定理来解决这种关系（例如将其近似为T(n) = 2T(3n/4) + cn）吗？或者，换句话说，这些子问题的大小是“本质上相同”还是已经“本质上不同”？

我正在阅读 Thomas H. Cormen 的书以理解 Master theorem 的证明。但是，我坚持证明 case-1。请通过更简单的数学推导来帮助我理解数学证明：

谢谢

我无法弄清楚 f(n) 是什么？是 n^2 还是 2n^2 + n/3 ？如何解决这些问题？提前致谢

试图解决这个递归：

但 f(n) 是常数 -sqrt(n)

我的问题：

1. 我可以假设 f(n) = Theta(sqrt n) 还是我应该知道一些技巧？

2. 另外，当你在这的时候，如果你能解释一下是否有一个常数减 sqrt(n) 即减号有什么意义吗？或者可以忽略。

这真让我抓狂！请帮忙！谢谢！！