作者avogau ( 假 装)
看板TransCSI
标题Re: [问题] 1题演算法问题
时间Fri Oct 24 18:00:51 2008
※ 引述《tool11 (:))》之铭言：
: Suppose that, in a divide-and-conquer algorithm, we always divide an instance
: of size n of a problem into 10 subinstances of size n/3, and the dividing and
: combining steps take a time in Θ(n^2). Write a recurrence equation for the
: running time T (n), and solve the equation for T (n).
: n为实例切成10个大小n/3的子实例 且分割与合并步骤花的时间在Θ(n^2)
: 求递回方程式T(n)以及解
: 这是我自己的算法 一下也卡住了
: T(n) = 10T(n/3)+ Θ(n^2)
: From the master theorem
: a=10
: b=3
: f(n) =Θ(n^2)
以上这一部分没有错
n^(logba) = n^(2.09...)
********(注一)
所以 取 e = 0.01
使得 f(n) = O( n^(logba - e ) )
=> T(n) = O( n^(logba) ) = O( n^(1/log3) )
注一:
(logba) 为 log 以b为底 数字为a
即 log a / log b
那个符号太难打了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.118.126.124
※ 编辑: avogau 来自: 140.118.126.124 (10/24 18:03)
※ 编辑: avogau 来自: 140.118.126.124 (10/24 18:04)
1F：推 tool11:^^ ３Ｑ 10/24 21:30
※ 编辑: avogau 来自: 114.45.62.46 (10/24 23:25)
2F：→ avogau:刚打错一小部分 修改一下 10/24 23:26