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

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

big-o recurrence algorithm

DevArenaCN · 技术社区 · 10 年前

T(m,n)=2T(m/2,n)+n,如果m<;2或n<2. 所以我不明白的是,这个问题能用主定理解决吗?如果是,如何?如果不是,这张表正确吗?

level   # of instances  size    cost of each level  total cost
0              1        m, n            n                n
1              2       m/2, n           n               2n
2              4       m/4, n           n               4n
i             2^i    m/(2^i), n         n             2^i * n
k              m        1, n            n               n*m

谢谢

1 回复 | 直到 10 年前

ead 10 年前

这里的主定理可能有点过分,你的解决方法也不错( log 指以对数为底 2 , c=T(1,n) ):

T(m,n)=n+2T(m/2,n)=n+2n+4T(m/4,n)=n*(1+2+4+..+2^log(m))+2^log(m)*c
      =n*(2^(log(m)+1)-1)+m*c=Theta(n*m)

如果你使用主定理 n 作为一个常数,比你容易得到的 T(m,n)=Theta(m*C(n)) 具有常数 C 取决于 n ,但主定理并没有告诉你多少关于这个常数 C 。如果你太聪明,注意力不集中,你很容易被烧伤:

T(m,n)=n+2T(m/2,n)=n*(1+2/nT(m/2,n))=n*Theta(2^(log(m/n)))
      =n*Theta(m/n)=Theta(m)

现在,因为你离开了 C(n) 第三步,你得到了一个错误的结果!

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前