Rekurencja

by Jerry Sky

2020-03-02

1°1\degree Metoda indukcyjna

T(n)=4⋅T(n2)+n T(n) = 4\cdot T\Big(\frac{n}{2}\Big) + n T(1)=Θ(1) T(1) = \Theta(1) Założenie indukcyjne: ∀k<n: T(k)≤c⋅k3 \forall{k<n}:~ T(k) \le c \cdot k^3 Robimy krok indukcyjny T(n)=4⋅T(n2)+n≤4c⋅n323+n= T(n) = 4\cdot T\Big(\frac{n}{2}\Big) + n \le 4c \cdot \frac{n^3}{2^3} + n = =c⋅n3+(−c⋅n32+n)≤c⋅n3 = c \cdot n^3 + \Big( -\frac{c \cdot n^3}{2} + n \Big) \le c \cdot n^3 przy czym (−c⋅n32+n)≤0 \Big( -\frac{c \cdot n^3}{2} + n \Big) \le 0 wówczas

−cn32+n≤0 -\frac{cn^3}{2} + n \le 0 cn22≥1 \frac{cn^2}{2} \ge 1

c=2,n0=1 c = 2, n_0 = 1 T(n)=O(n3) T(n) = O(n^3)

T(n)=O(n2) T(n) = O(n^2) Założenie indukcyjne ∀k<n: T(k)≤ck2 \forall{k < n}:~ T(k) \le ck^2 Krok indukcyjny T(n)≤4⋅cn222+n=cn2+n≰cn2 T(n) \le 4\cdot\frac{cn^2}{2^2} + n = cn^2 + n \not\le cn^2

Założenie indukcyjne ∀k<n:T(k)≤c1k2−c2k \forall{k < n }: T(k) \le c_1k^2 - c_2k Krok indukcyjny T(n)≤4(c1n24−c2n2)+n= T(n) \le 4\Big( c_1\frac{n^2}{4} - c_2 \frac{n}{2} \Big) + n = =c1n2−2c2n+n≤c1n2−c2n= = c_1n^2 - 2c_2n + n \le c_1n^2 - c_2n = c1n2−c2n+(c2n+n)≤c1n2+c2n c_1n^2 - c_2n + \big(c_2n + n\big) \le c_1n^2 + c_2n przy czym (c2n+n)≤0 (c_2n + n) \le 0 wówczas

−c2n+n≤0 -c_2n + n \le 0 c2≥1 c_2 \ge 1 T(1)≤c1−c2≥0 T(1) \le c_1 - c_2 \ge 0

T(n)=O(n2) T(n) = O(n^2)