问题标签 [master-theorem]

我正在尝试通过查看我的期中考试来准备考试。我不完全理解的一件事是主定理。我了解有三种情况，在这种情况下可以申请

T(n) = 25T(n/5) + n^(2)

但我的教授喜欢以这种形式给出一些

T(n) = {n+2 如果 n=0,1,2,3
T(n) = {4T(n-1) - 6T(n-2) + 4T(n-3) - T(n- 4) 否则

所以我很困惑是否有不同的方法来做主定理，或者我是否打算以某种方式将其更改为我理解的格式。

我的问题是关于Master theorem的。是否存在a >= 1和b > 1但主定理不起作用的情况？请你举个例子好吗？

我正在尝试解决一个练习，我必须用 at(n) ∈ Θ(n^3/2) 运行时编写一个代码片段。

我可以使用递归、加法、减法、整数除以 2、for 循环、if 语句、<、>、== 以及 if 和 return 语句。

要获得 t(n) ∈ Θ(n^3) 的运行时间，我只需要使用 3 个 for 循环，我也认为有这个规则，通过使用 if 语句，运行时间变成对数。我对如何获得 t(n) ∈ Θ(n^3/2) 的运行时间一无所知。

如果有人可以提供一些建议，我会非常高兴。谢谢 ：）

我正在使用 HOL-Z 中的数学工具包来释放一些 Isabelle 谓词。具体来说，我使用部分函数定义来定义我正在编写的 Z 规范中的一些关系，在其中我将模式转换为规范语句，以便我可以生成简单的 HOL 谓词。

来自 HOL-Z 工具包的定义

当我在谓词中编写以下内容时：

其中 balance 和 Bbalance 都是偏函数（在 Z 中），在 Isabelle 中的形式为 ('a <=> 'b)，我认为它表现良好。

我如何定义另一个函数，我说这两个部分函数对于所有 'x' 都是完全不相交的。我的意思是相同值在两个偏函数“balance”和“Bbalance”上的关系应用永远不会产生相同的值。就像是...

抱歉解释不佳。我们通过专家建议学习:)。

因此，在之前的考试中，我被要求在不使用主定理的情况下求解以下递归方程：

不幸的是，我在考试中无法弄清楚，所以我使用大师定理解决了它，这样我就可以知道答案（但是，当然，我没有得到这个问题的学分），现在我想知道如何在没有硕士定理的情况下解决它，因为在期末考试中，会有类似的问题。

如果有人可以提供一步一步的解决方案（带有解释），那就太好了，谢谢！

（分而治之）trominoes 算法的复杂性是什么或应该是什么？为什么？

我得到了一块 2^k * 2^k 大小的木板，其中一块瓷砖被随机移除，使其成为一块有缺陷的木板。任务是用“trominos”填充，这是一个由 3 个瓷砖组成的 L 形图形。

平铺问题

– 输入：一个 n × n 的正方形板，缺少一个 1 × 1 的正方形，其中对于某些 k ≥ 1，n = 2k。

– 输出：使用 tromino 的棋盘拼贴，通过从 2 x 2 正方形中删除右上角 1 x 1 角获得的三个正方形瓷砖。

– 您可以旋转 tromino，以平铺木板。基础案例：可以平铺一个 2 x 2 的正方形。

就职：

– 将正方形分成 4 个，n/2 x n/2 个正方形。

– 将tromino 放置在“中心”，tromino 不会与先前错过的 1 x 1 方块的 n/2 x n/2 方块重叠。

– 以感应方式求解四个 n/2 x n/2 板中的每一个。

我是一名在大学学习算法课程的学生。我知道如何应用一些递归技术来查找更简单函数的运行成本，但是2^n这个问题给我带来了麻烦。这是我尝试应用主定理的方法

a=1,b=2 n^log2(1)= n^0.65

这导致n^0=1我知道它必须是多项式乘以，f(N)但2^n我不明白这与 . 有什么可比性2^n。

我也尝试使用递归树，但它太复杂了。

我无法解决以下复发

我的工作：应用主定理

这导致n^0=1这与 l 无法比较og^2n

我也尝试使用递归树，但它太复杂了。请帮忙。

这里有一个问题。

我真的很困惑c等于0.5部分。其实总的来说我很困惑怎么logn会变成n^(0.5)。难道我不能让c等于100which 意味着100 < d使用不同的情况吗？我在这里想念什么？

So I've encountered a case where I have 2 recursive calls - rather than one. I do know how to solve for one recursive call, but in this case I'm not sure whether I'm right or wrong.

I have the following problem:

T(n) = T(2n/5) + T(3n/5) + n

And I need to find the worst-case complexity for this. (FYI - It's some kind of augmented merge sort)

My feeling was to use the first equation from the Theorem, but I feel something is wrong with my idea. Any explanation on how to solve problems like this will be appreciated :)