问题标签 [recurrence]

如何T(n) = T(n-1) + n使用迭代方法解决，答案是theta(n^2)

有谁知道如何解决这种复发？

主定理在这里不起作用。

问候，堆栈溢出。

假设我有两个用于计算S(i,j)的递归关系

我想以渐近最优的方式计算值S(0,0)、S(0,1)、S(1,0)、S(2,0)等。用铅笔和纸几分钟后发现它展开成树状结构，可以通过多种方式横切。现在，树以后不太可能有用，所以现在我正在寻找生成嵌套列表，如[[S(00)],[S(10),S(01)],[S(20),S(21),S(12),S(02)],...]. 我创建了一个函数来生成S(i,0)（或S(0,j)，取决于第一个参数）的平面列表：

然而，我不知道如何进一步进行。

我得到了这个递归关系：

C > 0 , a >= 1 ..

我的问题是 T (a) ，我不明白你怎么能“重复”一个常数？

就像，如果我想建立一个递归树，我会这样做：

你明白我的意思吗？T(a) 代表什么？

任何资源将不胜感激。谢谢。

或者，反复考虑：

如何解决这种重复：T(n) = T(n/2) + T(n/4) + O(1)

Master Method 似乎没有帮助，因为这不是T(n) = aT(n/b) + f(n). 我被困了很长一段时间。

我正在开发一个应用程序，它基本上会在用户需要对各种设备执行预防性维护时提示他们。每件设备（称之为工具）都有不同的重复模式。有些将基于时间，例如每 90 天，而另一些则基于其他因素，例如使用情况。例如，一个特定的工具在被检出 X 次后可能需要 PM。

所有工具都分配给一个人，因此当该用户登录应用程序时，我需要显示当时需要 PM 的工具列表。完成 PM 后，这些项目会从列表中删除，并且在其他情况下，例如日期更改或工具被放回婴儿床，工具将被添加。

我从将返回此列表的服务方法的设计开始，并正在寻找有关我用来解决列表中哪些项目的方法的一些帮助。对于输入，我将拥有用户的标识符和当前日期。从那里我需要查询工具列表并根据它们的重复模式确定上次执行 PM 的时间以及自上次 PM 以来发生的事件，该项目是否应该出现在列表中。

希望这是有道理的。我感谢任何关于我应该如何处理这个逻辑的想法和指导。

我知道如何为只调用一次自己的算法做递归关系，但我不确定如何做一次多次调用自己的事情。

例如：

我有以下问题：

求解使用大“O”符号简化答案的递推关系：

我知道这是一阶非齐次递归关系并且已经解决了这个问题，但我似乎无法获得基本情况的正确输出（f（0）= 2）。

该问题必须在证明中使用几何级数之和。

这是我的答案 -注意 sum(x = y, z) 是大写 sigma 表示法的替代品，其中 x 是初始化为 y 的总和的下限，z 是总和的上限：

首先，我确信第 11 行的等式可以进一步简化，其次，在 n = 0 中进行细分应该得到 2 作为结果。到达第 13 行时，我无法获得此答案...

编辑：我需要知道的是为什么在第 12 行将 n = 0 代入方程时我没有得到 f(0) = 2。另外我想知道的是如何简化 f(n) 的方程在第 12 行？

任何人...？

如果我对递归关系有以下封闭形式的解决方案，如何在大 O 下简化它：

f(n) = 3^n + n.9^n

我会冒险猜测：

f(n) 是 O(9^n) 的成员 -> 我不确定这是否正确？有人可以让我知道如何在大 O 下简化上述方程，并说明您使用的规则...

提前致谢

我必须从这个算法中找到递归方程：

我对此进行了推理并得出结论，如果 n<=2，则 T(n) = O(1)

我认为内部 while 是 O(n) （每次迭代时 j 减 1），而外部 while 是 O(logn) （每次迭代时 i 减半），给出 O(n*log( n)):

T(n) = T(n/3) + T(n/2) + O(n*log(n)) 如果 n > 2

这是一个很好的论点吗？