gpt4 book ai didi

algorithm - 解决类似的递归: T(n) = 3T(n/3) + n/3

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:23:37 24 4
gpt4 key购买 nike

鉴于..

T(0) = 3 for n <= 1

T(n) = 3T(n/3) + n/3 for n > 1

所以答案应该是 O(nlogn).. 我是这样做的,但它没有给我正确的答案:

T(n) = 3T(n/3) + n/3

T(n/3) = 3T(n/3^2) + n/3^2

将其代入 T(n) 给出..

T(n) = 3(3T(n/3^2) + n/3^2) + n/3

T(n/3^2) = 3(3(3T(n/3^3) + n/3^3) + n/3^2) + n/3

最终它会看起来像..

T(n) = 3^k (T(n/3^k)) + cn/3^k

设置k = lgn..

T(n) = 3^lgn * (T(n/3^lgn)) + cn/3^lgn

T(n) = n * T(0) + c

T(n) = 3n + c

虽然答案是 O(n)..我的步骤有什么问题?

最佳答案

T(n) = 3T(n/3) + n/3
T(n/3) = 3T(n/9) + n/9

T(n) = 3(3T(n/9) + n/9) + n/3
= 9T(n/9) + 2*n/3 //statement 1

T(n/9)= 3T(n/27) + n/27
T(n) = 9 (3T(n/27)+n/27) + 2*n/3 // replacing T(n/9) in statement 1
= 27 T (n/27) + 3*(n/3)

T(n) = 3^k* T(n/3^k) + k* (n/3) // eventually

用以 3 为底的 log n 替换 k。

T(n)  = n T(1) + (log n) (n/3);
// T(1) = 3
T(n) = 3*n + (log n) (n/3);
Hence , O (n* logn)

关于algorithm - 解决类似的递归: T(n) = 3T(n/3) + n/3,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23259404/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com