问题标签 [recurrence]

我正在尝试对以下递归函数执行渐近分析，以有效地为数字提供动力。由于在功率为奇数和功率为偶数时有不同的方程，我无法确定递推方程。我不确定如何处理这种情况。我知道运行时间是 theta(logn) 所以任何关于如何继续这个结果的建议都将不胜感激。

我正在尝试解决递归关系以找出我编写的算法的复杂性。这是等式。。

T(n) = T(n-1) + Θ(n)

我找到了 O(n2) 的答案，但我不确定我是否做对了。有人可以确认吗？

更新：如果方程是 T(n) = T(n-1)+Θ(nlogn) 怎么办？它仍然是O（n2）吗？

我想知道是否存在任何证明算法正确性的规则/方案？例如，我们在自然数上定义了一个函数 $F$，定义如下：

其中 $n \ \text{div}\ 2 = \left\lfloor\frac{n}{2}\right\rfloor$

任务是证明 $F(n,k)= \begin{cases} 1 \Leftrightarrow {n \choose k} \ \text{mod} \ 2 = 1 \ 0 \text{ else } \end{cases} $

它看起来不是很复杂（我错了吗？），但我不知道这种证明应该如何构建。我将非常感谢您的帮助。

我一直在研究这种反复出现并想检查我是否采取了正确的方法。

所以答案将是 n^(1/2) 的 theta 界

需要帮助找到解决以下问题的方法：
给予所有人。 并给出. 解决 我尝试了主定理，但所有 3 种情况都不适合这里，我的猜测是使用替换方法，但我不确定如何应用它f(n)9f(n/3)+(n2)*(log3n)n > 1
f(1)=1
f(n)

我知道递归关系的公式是 T(n)=aT(n/b)+f(n)。鉴于这个方程，我知道如何求解 BigO。我的作业问题要求我编写一个递归函数来计算列表中的节点数，我这样做了，但后来要求我编写一个递归关系。这是我的代码：

但是我完全不知道如何创建/制定我自己的递归关系公式......我如何找到a或b......我不知道从哪里开始。如何编写此函数的递归关系？谢谢你。

我正在准备数据结构/算法考试，我想做一些练习问题来处理递归函数的递归关系和代码片段的大 O 运行时间......谁能指出我正确的方向（在线资源首选）？

我想创建一个每 x 周和特定工作日运行的 cron 作业。例如：在每周日和周一的午夜每 2 周运行一次。

为每个“计划”存储 cron 表达式，我使用SQL Server 2008 中的ncrontab函数来生成给定 cron 表达式的日期。

有表达吗？甚至几个表达式的连接？

我尝试使用以下表达式，但它总是在几个月内给出相同的日期

编辑：
我一直在寻找每 x 天/周的重复频率，而 cron 的主要问题是它每次都将重复频率重置为每月的第一天。例如，如果我每 3 天在 29 日开始重复，则下一次将是下个月的第一天。

我已经忽略了下一个解决方案的 cron：http: //www.codeproject.com/Articles/20343/Recurring-Date-Generator-with-Pattern-Coding

我有一组重复发生的事件。我需要能够计算出这些事件在接下来的 5 周左右发生的时间。

本系统将通知用户，在本月内，将发生这些事件。

例如：

事件1

• 开始日期= 2011 年 12 月 19 日星期一
• 重复模式= 星期一/两周一次

事件2

• 开始日期= 2012 年 2 月 3 日星期四
• 重复模式= 星期四/每三周

现在是 3 月 22 日——在接下来的 5 周内，事件 1 和 2 的日期是什么。

能够检测是否是圣诞节也很有用，那么活动将推迟到另一天。

我正在使用.NET MVC2，但我想这是偶然的。

感谢您的帮助

在 Math.SE 上回答，为递归关系生成矩阵

对于递归f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)，如何获得生成矩阵以便可以通过矩阵求幂来求解？

对于f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)相应的生成矩阵为：

那么如何为所需的重复次数获得相同的结果？还有可能是以下形式的任何复发的程序应该是什么：

f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+..+someconstant*f(n-k)?

谢谢。