algo/algo.org

algo

• Orga
• 18.10.2019 2.VL
  • Merge Sort: \(T(n) = 2 T(\fraq{n}{2}) + n\)
  • Binäre Suche
  • Mastertheorem:
  • Bsp:

Orga

• Klausur Fr 07.02.2020 14-16 Uhr
• Nachklausur: Mo 06.04.2020 14-16 Uhr

18.10.2019 2.VL

Merge Sort: \(T(n) = 2 T(\fraq{n}{2}) + n\)

Beh: T(n) = 0(n * log(n)) Bew: \( T(2) = 1 \le O(2n*log\,2) = o(1)\) n/2 -> n:_ \(T(n) \le 2 * c * \fraq{n}{2} * log(\fraq{n}{2}) + n)\) \(T(n) \le c * n * log(\fraq{n}{2}) + n)\) \(\le c * n * (log n - log 2) + n\ \(< c * n * log n - c * n + n \leq c * n * log(n)\)

Binäre Suche

Beh: T(n) = O(log n) Bew: I.A: \(\begin{equation} T(2) = 2 = O(1) \\ \fraq{n}{2} \rightarrow n \colon T(n) &\le c * log (\fraq{n}{2}) + 1\\ &= c * (log n - log 2) + 1\\ &= c * log n - c +1\\ &\leq c * log n \end{equation}\) für c ≥ 1

Mastertheorem:

log_ba = log₂ 2 = 1 f(n) = n = n^_1_ ⇒ T(n) = O(n^{1 * log_2*^{}n)

1. T(n) = 9 * T (\fraq{n}{3} * + n² → log_ba = log₃9 = 2 f(n) = n² = n^{log₃9} = 2 f(n) = n² = n^{log₃9 ⇒ T(n) = O(n² * log₃n) = O(n² log(n) f(n) = n = n^2-1 ⇒ T(n) = O(n²)

Bsp:

1. \(T(n) = 4 * T (n/2) + n\\ log_{2} 4 = 2\,\,f(n) = n \le n^{2-\epsilon} \rigtharrow T(n) = O(n^{2})\) für ε = 1/2
2. \( T(n) (\fraq{n}{2}) + n^{3/2} \le Tn^{2- \epsilion} \Rightarrow t(n) = O(n^{2}) \)
3. \( T(n) (\fraq{n}{2}) + n² f(n) = n² = n^{log_ba} ⇒ T(n) =

O(n² * log n\)

1. \( T(n) (\fraq{n}{2}) + n³ f(n) = n³ > n^{2+ ε} ⇒ T(n) = o (f(n))

= O(n³) \)

1. \(T(n) = 8 * T(\frqa{n}{2} + n^{1} \rightarrow [1.] O(n^{3})\)
2. \(T(n) = 8 * T(\frqa{n}{2} + n^{³} \rightarrow[2.] O(n^{3} * log n)\)

T(n) = 2 * T(n/2) + n^{1 + ε} , ε > 0 ⇒ [3.] T(n) = O(n^1+ε) T(n) = 2 * T(n/2) + n log n < n¹+ε ∀ ε > 0 ⇒ M.T. nicht anwendbar