反復関係の誘導による証明

Question

アルゴリズムの時間複雑さを見つけるさまざまな方法を分析しており、誘導による証明を使用してこの特定の反復関係を解くことに多くの困難を抱いています。

私のRRは次のとおりです。 T（n）が< = 2T（N/2）+√N

私はあなたが仮定のnとn-1を証明すると仮定していますか？誰かが私を助けることができますか？

Answer 1

T（0）= 0、T（1）= 1と仮定しましょう。 T（2）= 3.41、T（4）= 8.82、T（6）= 14.57、T（8）= 20.48、T（10）= 26.51となる。これは線形関数のようです。

そこで、我々は、これは誘導によって証明することができT(n) <= C * n + o(n).

を想定できます。それぞれk<nに対してT(k) <= C*(k) + o(k) = C*(k) + o(n).とします。

私達は証明するべきですT(n) <= C*n + o(n). 再発を使用して、T(n) <= 2*T(n/2) + sqrt(n) <= 2*(C*(n/2) + o(n)) + sqrt(n) = C*n + (2*o(n) + sqrt(n)) = C*n + o(n)。

このように、T(n) <= C*n + o(n)が証明されており、T(n)が少なくともO(n)であることが保証されています。

また、T(x) = 2T(x/2) + sqrt(x), T(0)=0, T(1)=1の溶液がT(x) = (2x-sqrt(2x))/(2-sqrt(2))であることがわかる。

Answer 2

誘導を使って証明すると仮定すると、Kは仮定され、2 * kまたは2^kが証明されます。

>First, check for T(1) : 
> T(1) <= 2T(1/2) + √n 
>(Assuming T(1/2) = 1) 
>T(1) = 2 + √n <= O(√n log n) 
> 
>Now, assuming it to be true for T(k). 
> => T(k) <= O(√n log n) 
>T(k) <= 2T(k/2) + √n <= c(√n log n) 
> 
> Proving for, T(2k): 
> T(2k) <= 2T(2k/2) + √(2k) 
> => T(2k) <= 2(c(√k log k) + √(2k) 
> => T(2k) <= √2 * [2(c(k log k) + √(2k)] //(Inequality follows) 
> => T(2k) <= [c'(2k log 2k)] 
> => T(2k) <= O(√n log n) 

成長速度： （<√N< N < NログNログN < NN log2nログ< C N < < N（1.1）< N2 < N3 < N4 < 2N）