Divide and conquer

by Jerry Sky

2020-03-09



Binary search(x,A)(x, A)

AA - posortowana tablica

  1. Dziel: porównujemy xx ze środkowym elementem z AA
  2. \lor \downdownarrows
    1. Jeśli x==A(n2)x == A\big(\frac{n}{2}\big) \rightarrow kończymy
    2. Jeśli x<A(n2)x < A\big(\frac{n}{2}\big) \rightarrow Binary Search( x,A[1...,n21] )\Big(~x, A\big[1..., \frac{n}{2} -1\big]~\Big)
    3. Oth x>A(n2)x > A\big(\frac{n}{2}\big) \rightarrow Binary Search( x,A[n2,...,n] )\Big(~x, A\big[\frac{n}{2}, ..., n\big]~\Big)

Worst case analysis

T(n)=O(1)+T(n2)T(n) = O(1) + T(\frac{n}{2})  T(n)=O(logn)\rightarrow~T(n) = O(\log n) z Master theorem

Podnoszenie do potęgi xnx^n

\rightarrow n razy: xxx...xx \cdot x \cdot x \cdot ... \cdot x \rightarrow #mnożeń =O(n)= O(n)

Divide and conquer case

xn={xn2xn2:n%2=0xn12xn12x:oth x^n = \begin{aligned} \begin{cases} x^{\frac{n}{2}} \cdot x^{\frac{n}{2}} &: n \% 2 = 0\\ x^{\frac{n-1}2} \cdot x^{\frac{n-1}{2}} \cdot x &: oth \end{cases} \end{aligned} T(n)=1T(n2)+O(1)=O(logn)T(n) = 1\cdot T(\frac{n}{2}) + O(1) = O(log n)

Liczenie nn-tej liczby Fibonacciego

Fn={0:n=01:n=1Fn1+Fn2:oth F_n = \begin{aligned} \begin{cases} 0 &: n = 0\\ 1 &: n =1\\ F_{n-1} + F_{n-2} &: oth \end{cases} \end{aligned}

Brute force

Θ(ϕn)\Theta(\phi^n), gdzie ϕ=1+52\phi = \frac{1 + \sqrt{5}}{2}

Podejście bottom-up

F2,F3,F4,...FnF_2, F_3, F_4,...F_n \rightarrow Θ(n)\Theta(n)

Fn=15ϕn±15(152)nF_n = \frac{1}{\sqrt{5}} \phi^n \plusmn \frac{1}{\sqrt{5}}\Big(\frac{1- \sqrt{5}}{2}\Big)^n  O(logn)\rightarrow~O\big(\log n\big) mnożeń \rightarrow przybliżenie z 5\sqrt{5}