Drzewo rekursji

by Jerry Sky

2020-03-09

T(n)=T(n2)=T(n4)+n2T(n) = T\big(\frac{n}{2}\big) = T\big(\frac{n}{4}\big) + n^2, T(1)=Θ(1)T(1) = \Theta(1)

<insert tree>

→\rightarrow rozmiar

  1. n2n^2 →\rightarrow nn
    1. (n2)2(\frac{n}{2})^2 →\rightarrow n2+n4\frac{n}{2} + \frac{n}{4}
      1. (n4)2(\frac{n}{4})^2 →\rightarrow n4+2⋅n16\frac{n}{4} + 2 \cdot \frac{n}{16}
      2. (n8)2(\frac{n}{8})^2 →\rightarrow n4+2⋅n16\frac{n}{4} + 2 \cdot \frac{n}{16}
    2. (n4)2(\frac{n}{4})^2 →\rightarrow n2+n4\frac{n}{2} + \frac{n}{4}
      1. (n8)2(\frac{n}{8})^2 →\rightarrow n4+2⋅n16\frac{n}{4} + 2 \cdot \frac{n}{16}
      2. (n16)2(\frac{n}{16})^2 →\rightarrow n4+2⋅n16\frac{n}{4} + 2 \cdot \frac{n}{16}

Koszt:

  1. n2n^2
  2. n2⋅1516n^2 \cdot \frac{15}{16}
  3. n2⋅25256=n2⋅(516)2n^2 \cdot \frac{25}{256} = n^2 \cdot (\frac{5}{16})^2
  4. n2⋅(516)3n^2 \cdot (\frac{5}{16})^3

<insert tree>

height=log⁡n+1height = \log n +1

n2x=1\frac{n}{2^x} = 1
x=log⁡2nx = \log_2n

mamy ∑j=0∞qj=11−q\sum_{j=0}^{\infin}q^j = \frac{1}{1-q} dla ∣q∣<1|q| < 1

T(n)≤∑k=0log⁡nn2⋅(516)k≤n2⋅∑k=0∞(516)k=1611n2T(n) \le \sum_{k=0}^{\log n}n^2 \cdot (\frac{5}{16})^k \le n^2 \cdot \sum_{k=0}^{\infin}\big(\frac{5}{16}\big)^k = \frac{16}{11} n^2

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

∑k=0log⁡nn2⋅(516)k=n2(1611−5⋅(516)log⁡n)=\sum_{k=0}^{\log n}n^2 \cdot (\frac{5}{16})^k = n^2(\frac{16}{11} - 5\cdot (\frac{5}{16})^{\log n})=
n2(1611−5⋅nlog⁡516)n^2(\frac{16}{11} - 5\cdot n^{\log \frac{5}{16}}), log⁡(516)=−1.67\log(\frac{5}{16}) = -1.67