Binary search(x,A)
A - posortowana tablica
- Dziel: porównujemy x ze środkowym elementem z A
- ∨ ⇊
- Jeśli x==A(2n) → kończymy
- Jeśli x<A(2n) → Binary Search( x,A[1...,2n−1] )
- Oth x>A(2n) → Binary Search( x,A[2n,...,n] )
Worst case analysis
T(n)=O(1)+T(2n) → T(n)=O(logn) z Master theorem
Podnoszenie do potęgi xn
→ n razy: x⋅x⋅x⋅...⋅x → #mnożeń =O(n)
xn={x2n⋅x2nx2n−1⋅x2n−1⋅x:n%2=0:oth T(n)=1⋅T(2n)+O(1)=O(logn)
Liczenie n-tej liczby Fibonacciego
Fn=⎩⎪⎪⎨⎪⎪⎧01Fn−1+Fn−2:n=0:n=1:oth
Brute force
Θ(ϕn), gdzie ϕ=21+5
Podejście bottom-up
F2,F3,F4,...Fn → Θ(n)
Fn=51ϕn±51(21−5)n → O(logn) mnożeń → przybliżenie z 5