问题标签 [master-theorem]

我对 Master Theorem 有点耳目一新，我试图找出一种算法的运行时间，该算法n通过递归解决 2 个大小子问题n-1并在恒定时间内组合解决方案来解决大小问题。
所以公式是：
T(N) = 2T(N - 1) + O(1)
但我不确定如何制定主定理的条件。我的意思是在这种情况下
我们没有主定理公式吗？ 如果是的话，因为很明显，因为我在哪里可以理解这一点？假设我到目前为止是对的？T(N/b)bb=N/(N-1)
a > b^kk=0O(N^z)z=log2(N/N-1)

我在如何解决重复关系方面遇到了一些问题。

T(n) = T(n/2) + log2(n)，T(1) = 1，其中 n 是 2 的幂

这是一个家庭作业问题，所以不要只给我答案。我只是想知道如何开始这个问题。

在课堂上，我们复习了 Master 定理。但我认为这不是解决这种特殊关系的最佳方式。

我真的不知道如何开始这个问题......我应该去吗

并且继续努力得到一些我可以看到的东西构成一个基本方程？

请注意，这是家庭作业。

我需要找到数组的模式（正值），然后如果模式大于sizeof(array)/2主导值，则返回该值。有些阵列两者都没有。这很简单，但是有一个约束条件是在确定之前不能对数组进行排序，此外，复杂度必须在 O(nlogn) 的数量级上。

使用第二个约束和主定理，我们可以确定时间复杂度 'T(n) = A*T(n/B) + n^D' 其中 A=B 和 log_B(A)=D 对于 O(nlogn ） 是真实的。因此，A=B=D=2。这也很方便，因为主导值必须在数组的第一、第二或两半中占主导地位。

使用 'T(n) = A*T(n/B) + n^D' 我们知道搜索函数将在每个级别 (A) 调用自身两次，在每个级别 (B) 将问题集除以 2。我一直在弄清楚如何让我的算法考虑到每个级别的 n^2。

制作一些代码：

我在这里缺少的“胶水”是如何组合这些划分的功能，我认为这将实现 n^2 复杂性。这里有一些技巧，其中主导必须是第一或第二半或两者中的主导，不太确定这如何帮助我现在解决复杂性约束。

我已经写下了一些小数组的例子，并且我已经画出了它的划分方式。我似乎无法找到一个始终返回主导值的单一方法的正确方向。

在级别 0，函数需要调用自身来搜索数组的前半部分和后半部分。这需要递归，并调用自己。然后在每一层，它需要执行 n^2 次操作。因此，在数组 [2,0,2,0,2] 中，它会将其拆分为对 [2,0] 的搜索和对 [2,0,2] 的搜索并执行 25 次操作。在 [2,0] 上的搜索将调用在 [2] 上的搜索和在 [0] 上的搜索并执行 4 次操作。我假设这些需要搜索数组空间本身。我打算使用 C++ 并使用 STL 中的东西来迭代和计算值。我可以创建一个大数组，并通过它们的索引更新计数。

所以问题是找出 x 是否在按行和按列升序的排序矩阵的元素之一中。

例子 ：

1 2 3

4 5 6

7 8 9

我有兴趣找到这个问题的分而治之解决方案的时间复杂度。我用谷歌搜索了它，但我只找到了 O(m+n) 解决方案，并且还从这个Search a sorted 2D matrix中找到了。但他说（对答案发表评论）“T(R) = 3T(R/4)”，为什么 f(R) = 0？

问题是使用主定理的分而治之解决方案的复杂性是什么？在 T(R) = 3T(R/4) + f(R) 中，f(R) 应该是多少？

如果有帮助，这是我的分而治之的解决方案：

编辑以澄清解决方案：

算法： 1. 将矩阵的中间元素与搜索值进行比较 2. 如果值等于 m(i,j)，则返回 true 3. 如果值较小，则搜索矩阵的右上角、左上角、左下角的值矩阵 4. 如果值较大，则在矩阵的右上角、右下角、左下角搜索值

我有一个递归关系，如下所示：

T(e ⁿ ) = 2(T(e ^n-1 )) + e ⁿ，其中 e 是自然对数。

为了解决这个问题并找到一个 Θ 界限，我尝试了以下方法：我输入 k=en ^，等式转换为：

T(k)=2T(k/e)+k

然后，我尝试使用主定理。根据主定理，a=2，b=e>2，f(k)=k。因此，对于某些 ε>0，我们有 f(k)=Ω(n ^{log _b a+ε} ) 的情况，因此我们有 T(k)=Θ(f(k))=Θ(k)。然后设 k=n，我们有 T(n)=Θ(n)。我的解决方案有任何错误吗？

刚刚在测验中得到了这个：T(n) = 4T(sqrt(n)) + 5

我使用替换简化它并得到 F(k) = 4F(k/2) + 5

使用主定理，我猜它是 O(logn)。这是准确的吗？

对于硕士定理T(n) = a*T(n/b) + f(n)，我使用了 3 种情况：

1. 如果a*f(n/b) = c*f(n)对于某个常数c > 1那么T(n) = (n^log(b) a)
2. 如果a*f(n/b) = f(n)那时T(n) = (f(n) log(b) n)
3. 如果a*f(n/b) = c*f(n)对于某个常数c < 1那么T(n) = (f(n))

但是当f(n) = log n或时n*log n， 的值c取决于 n 的值。如何使用大师定理解决递归函数？

我已经使用主定理来解决递归关系。我已经把它归结为Θ(3n ² -9n)。这是否等于Θ(n ² )？我有另一个递归，其解决方案是Θ(2n ³ - 100 ² )。在 BigTheta 表示法中，您总是只使用最大的项吗？所以我的第二个是Θ(n ³ )？在第二种情况下，似乎100n ²会更重要。那么我丢弃它有关系吗？

有什么建议么？

我如何理解主定理，算法可以递归定义为：

其中a是子问题的数量，n/b是子问题的大小，O(n^d)是子问题的重组时间。计算主定理的时间复杂度如下：

我的问题是，如果重组时间不是以 O(n^d) 的形式表示怎么办？例如 O(2^n) 或 O(log(n))。如何确定时间复杂度？

我尝试从 Mergesort 计算复杂度。标准合并排序具有递归 T(n) = T(n/2)+T(n/2)+n 所以它很容易用主定理计算。

但我的问题是，如何计算 T(n) = T(2n/3) + T(n/3) + n 和 T(n) = T(n-100) + T(100) 的合并排序？

你们能帮帮我吗？谢谢 =)