私は持っています: T(n) = T(n/2) + T(n/4) + T(n/8) + cn; c > 0。
これは私の誘導ステップです: T(n) が O(n) にあることを証明したい、つまり、いくつかの d > 0 および n0 であるため、すべての n > n0 および T(n) < dn
T(n) = T(n/2) + T(n/4) + T(n/8) + cn <= d(n/4) + d(n/4) + d (n/8) + cn = dn(7/8) + cn = dn(7/8) + cn <= dn ... = 8c <= d
私はベースケースで行き詰まりましたが、これは私の先生が私にそれを説明した方法です: n0 = 8 T(8) = T(4) + T(2) + T(1) + c8 <= 8T(4) + 8T(2) + 8T(1) + C8 < d8 を試してください。
誰かが私に基本的なケースを説明できますか? ありがとうございました！