代码之家 › 专栏 › 技术社区 › Thunfische

与主定理的递推关系:多项式函数

recurrence algorithm

Thunfische · 技术社区 · 7 年前

允许 T(n)

T(n) = aT(n/b)+f(n)

a >= 1 和 b >= 2

使用 Master theorem ,必须满足的条件之一是 f(n) 应该是多项式函数。

在这个例子中,显然不是这样

T(n) = 2T(n/4) + n^(1/2) + 42 .

这本书很重要 f(n)=n^(1/2) 作为多项式函数,但我学到的是如果 f(n) = n^a 是一个多项式函数,那么 a 必须是自然数。有特殊情况吗?

1 回复 | 直到 7 年前

Thomas Ahle 7 年前

你可以称之为广义多项式,但这正是它的用意。许多适用于“自然数”多项式的定理也适用于这些广义多项式。只要想想差异化或集成。

推荐文章

Roman · 有没有办法在numpy中实现无for循环的递归?

6 年前

Smeagol · Prolog中存储在列表中的重复结果

6 年前

Thunfische · 与主定理的递推关系:多项式函数

7 年前

user7493003 · 时间复杂度和递归关系

7 年前

Alviss Min · 递推方程的时间复杂度

7 年前

Nawed Khan · 如何使用Outlook REST API在重复周期中创建异常

7 年前

AdamK · 如何从算法中找到递归关系

7 年前

h3rm8 · 如何为给定的DFA在一组q状态上提出递推方程?

8 年前

DevArenaCN · 计算2个递归调用的大Theta边界

8 年前

cstac · 复杂度算法递推关系

8 年前