推 tool11:^^ ３Ｑ 10/24 21:30
※ 編輯: avogau 來自: 114.45.62.46 (10/24 23:25)
→ avogau:剛打錯一小部分 修改一下 10/24 23:26
※ 引述《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)