问题标签 [recurrence]

我正在尝试解决 T(n) = 2T(n/2) + log n

替换 n = 2^k

所以基本上我需要对 i*2^i 的一项求和，其中 i = 1 以记录 n - 1。
我找不到一种简单的方法来总结这些项。难道我做错了什么 ？有没有其他方法可以解决这个递归？掌握定理对她有用吗？如果是，比如何？

谢谢。

在我的数据结构课程中，我们正在研究 T(n) 和大 O 问题 O(n) 之类的递归关系。我很感激学习这些的任何资源，我的教科书没有涵盖 T(n)，教授跳过了很多步骤。

我还没有看到解决这些问题的好方法。我意识到每个问题都是独一无二的，但必须有某种框架来解决这些问题。

谢谢。

我正在尝试RecurrenceTable在 Mathematica 中使用条件语句，递归的东西工作正常，但它不会完全评估它。

这些是正确的结果，但我需要它是数字形式，即{{0.25, 0.}, {0.25, 0.5625} ...

有没有办法做到这一点？谢谢！

我尝试使用该公式实现贝塞尔函数，这是代码：

但是如果我使用 MATLAB 的 bessel 函数将它与这个函数进行比较，我会得到太高的不同值。例如，如果我输入 Bessel(20) 它会给我 3.1689e+005 作为结果，如果我输入 bessel(20,1) 它给我 3.8735e-025 ，这是一个完全不同的结果。

我正在尝试解决这种重复

T(n) = 3 T(n/2) + n lg n ..

我已经得出它属于大师定理案例 2 的解决方案，因为 n lg n 是 O(n^2)

但在参考解决方案手册后，我注意到他们有这个解决方案

该解决方案说 n lg n = O ( n ^(lg 3 - e)) 对于 e 在 0 和 0.58 之间

所以这意味着 n lg n 是 O(n) .. 对吗？我在这里错过了什么吗？

不是 nlgn O(n^2) 吗？

给定一段代码，您将如何确定一般的复杂性。我发现自己对大 O 问题感到非常困惑。例如，一个非常简单的问题：

TA 用类似组合的方式解释了这一点。像这样 n 选择 2 = (n(n-1))/2 = n^2 + 0.5，然后删除常数，使其变为 n^2。我可以输入 int 测试值并尝试，但是这种组合的东西是怎么进来的？

如果有 if 语句怎么办？复杂度如何确定？

那么递归呢...

我有一个测试即将到来，我需要一些练习问题的帮助......需要通过归纳来证明这一点：

递归关系：m(i) = m(i-1) + m(i - 3) + 1, i >= 3 初始条件：m(0) = 1, m(1) = 2, m(2) = 3

证明 m(i) >= 2^(i/3)

到目前为止，这是我能够做到的：

基本情况： m(3) >= 2 -----> 5 >= 2。因此它适用于基本情况。

归纳假设假设存在 ak 使得 m(k) >= 2^(k/3) 成立。

现在我必须证明它对 k+1 成立。

所以我们有： m(k+1) >= 2^((k+1)/3)

等于（通过替换假设）：

m(k) + m(k-2) + 1 >= 2^((k+1)/3)

这就是我卡住的地方。我不知道从这里去哪里。任何帮助将不胜感激。多谢你们！

这个问题来自 2011 Codesprint ( http://csfall11.interviewstreet.com/ )：

计算机科学的基础之一是了解数字如何在 2 的补码中表示。想象一下，您使用 32 位以 2 的补码表示形式写下 A 和 B 之间的所有数字。你一共要写多少个1？输入：第一行包含测试用例的数量 T (<1000)。接下来的 T 行中的每一行都包含两个整数 A 和 B。 输出：输出 T 行，一个对应于每个测试用例。约束：-2^31 <= A <= B <= 2^31 - 1

样本输入：3 -2 0 -3 4 -1 4 样本输出：63 99 37

解释：对于第一种情况，-2 包含 31 个 1，后跟一个 0，-1 包含 32 个 1，0 包含 0 个 1。因此总数为 63。对于第二种情况，答案是 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到您可以使用 -X 中 1 的数量等于 (-X) = X-1 的补码中 0 的数量这一事实来加快搜索速度。该解决方案声称存在用于生成答案的 O(log X) 递归关系，但我不明白。解决方案代码可以看这里：https ://gist.github.com/1285119

如果有人能解释这种关系是如何得出的，我将不胜感激！

如果对于 T 中的每个节点 m，二叉树 T 是半平衡的：

R(m)/2 <= L(m) <= 2*R(m),

其中 L(m) 是 m 的左子树中的节点数，R(m) 是 m 的右子树中的节点数。

(a) 写一个递推关系来计算具有 N 个节点的半平衡二叉树的数量。

(b) 提供一个动态规划算法来计算 (a) 中的递归。

我该如何为此建立递归关系？

以下是否符合条件？

我猜他是在问更多的递归关系，比如函数之类的。？

另外，我该如何使用动态编程来解决问题？我想如果我应用上面建议的代码片段，我不需要存储任何东西。

请帮忙。

我有这个复发：

我的尝试如下：

树是这样的：

• 树的高度：(n/(2 ^h ))-1 = 1 ⇒ h = lg n - 1 = lg n - lg 2
• 最后一级的成本：2 ^h = 2 ^{lg n - lg 2} = (1/2) n
• 直到级别 h-1 的所有级别的成本：Σ _{i=0,...,lg(2n)} n - (2 ⁱ -1)，这是一个几何级数，等于 (1/2)((1/2 )n-1)

所以，T(n) = Θ(n lg n)

我的问题是：对吗？