AuK/Asymptotische Aufwandsordnungen/Übungsaufgaben und Lösungshinweise

Wiki-Quelltext dieser Seite.

<language>Python</language>
==Asymptotische Aufwandsordnungen==

===1. Die Funktionen sind von oben nach unten aufsteigend sortiert.===

====a)====
    
$$
    \begin{align*}
    f_1(n) &= n^{0.999999} \log n \\
    f_2(n) &= 10000000n \\
    f_4(n) &= n^2 \\
    f_3(n) &= 1.000001^n \\
    \end{align*}
    $$
    
====b)====

$$
    \begin{align*}
    f_1(n) &= 2^{2^{1000000}} \\
    f_4(n) &= n \sqrt{n} \\
    f_3(n) &= \binom{n}{2} \\
    f_2(n) &= 2^{1000000n} \\
    \end{align*}
    $$

====c)====
    
$$
    \begin{align*}
    f_4(n) &= \sum_{i=1}^n (i + 1) \\
    f_1(n) &= n^{\sqrt{n}} \\
    f_3(n) &= n^{10} \cdot 2^{\frac{n}{2}} \\
    f_2(n) &= 2^n \\
    \end{align*}
    $$
    
===2.===
====a)====
$\mathcal{O}(n)$
    
====b)====
$\mathcal{O}(n^2)$
    
====c)====
$\mathcal{O}(n \cdot m)$
    
====d)====
$\mathcal{O}(n)$
    
====e)====
$\mathcal{O}(n)$
    
====f)====
$\mathcal{O}(n)$
    
====g)====
$\mathcal{O}(\log n)$
    
====h)====
$\mathcal{O}(\log n)$
    
===3.===
====a)====
$$
    \begin{align}
    \\
    \text{Behauptung: } & \max(f(n), g(n)) \in \Theta(f(n) + g(n)) \\
    \\
    \text{Fallunterscheidung: } & \\
    \\
    \max(f(n), g(n)) = f(n) : \\
    \\
    g(n) < f(n) & \implies f(n) + g(n) < 2 \cdot f(n) \\
    \implies f(n) > \frac{1}{2} (f(n) + g(n)) & \implies f(n) \in \Omega(f(n) + g(n)) \\
    \implies \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \\
    \\
    f(n) \leqslant f(n) + g(n) \text{, mit $g(n) \geqslant 0$ } & \implies f(n) \in \mathcal{O}(f(n) + g(n)) \\
    \implies \max(f(n), g(n)) & \in \mathcal{O}(f(n) + g(n)) \\
    \\
    \max(f(n), g(n)) = g(n) : \\
    \\
    g(n) < f(n) & \implies f(n) + g(n) < 2 \cdot g(n) & \\
    \implies g(n) > \frac{1}{2} (f(n) + g(n)) & \implies g(n) \in \Omega(f(n) + g(n)) \\
    \implies \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \\
    \\
    g(n) \leqslant g(n) + f(n) \text{ mit $f(n) \geqslant 0$ } & \implies g(n) \in \mathcal{O}(f(n) + g(n)) \\
    \implies \max(f(n), g(n)) & \in \mathcal{O}(f(n) + g(n)) \\
    \\
    \max(f(n), g(n)) \in \mathcal{O}(f(n) + g(n)) \land \max(f(n), g(n)) & \in \Omega(f(n) + g(n)) \implies \max(f(n), g(n)) \in \Theta(f(n) + g(n))
    \end{align}
    $$
    
    
====b)====
    
$$\text{Behauptung: } \frac{1}{\Omega(n)} \in \mathcal{O} \left( \frac{1}{n} \right)$$
$$\frac{1}{\Omega(n)} < \frac{1}{c''1 \cdot n} \text{, mit $\Omega(n) > 1$ } = \frac{1}{c''1} \cdot \frac{1}{n} = c_2 \cdot \frac{1}{n} \text{, mit $c_2 = \frac{1}{c_1}$ } \in \mathcal{O} \left( \frac{1}{n} \right)$$
    
   
===4.===
====a)====
<code id="5fd805d996dd3">
def find_index(iterable, value):
    for i in range(len(iterable)):
        if iterable[i] == value:
            return i


def car_parking(src, tgt):
    operations = []
    for i in range(len(tgt)):
        if src[i] != tgt[i]:
            if src[i] != 0:
                other_index = find_index(src, 0)
                operations.append((src[i], 0))
                src[i], src[other_index] = src[other_index], src[i]
            other_index = find_index(src, tgt[i])
            operations.append((src[other_index], 0))
            src[i], src[other_index] = src[other_index], src[i]
    return operations
</code>
<run id="5fd805d996e59"></run>

====b)====
$\mathcal{O}(n^2)$


===5.===

Diese Tabelle muss jeder Informatikstudierende einmal in seinem Leben aufgestellt und ausgefüllt haben!