Cvičení 02

# Programování II pro matematiky

## Teoretické cvičení 02

**10. 3. 2021**

Martin Mareš a Tomáš Karella

---

## Plán cvičení

- Opakování pojmů

- Hledání kuličky (Příklad 4 ze cvičení 1)

- Časová a prostorová složitost

- Příklady na určení složitosti

- Počítání s asymptotickou časovou složitostí

---

## Opakování - Teorie

- Algoritmus (co my od něj chceme na _p2m_)

- Skládá se z nějakých elementárních kroků
  - Skončí po konečném množství kroků 
  - Vrátí správný výsledek

- Porovnání algoritmů

- Časová složitost

- "... počet kroků v závislosti na velikosti vstupu"
    	- např. Kolik vážení musíme provést, abychom našli nejmenší kuličku v závislosti na počtu kuliček.

- Prostorová složitost
	
    	- "... kolik paměti zaberu v závislosti na velikosti vstupu"
    	- např. Kolik informací si musíme poznamenat, abychom našli nejmenší kuličku.

---

## Opakování - složitost

- $\mathcal{O}$ notace ("velké O"): Nechť $f, g:\N→\R$ jsou dvě funkce. Řekneme, že funkce $f(n)$ je třídy $\mathcal{O}(g(n))$, jestliže existuje taková kladná reálná konstanta $c$, že existuje nějaké přirozené $n_0$ takové, že pro všechna $n≥n_0$ platí $f(n)≤c \cdot g(n)$.
  $$
  f(n) \in \mathcal{O}(g(n)) \iff  \exist c > 0 ~ \exist n_o ~ \forall n \ge n_0: f(n) \le c \cdot g(n)
  $$

![Big-O example](./imgs/501211c02f4c6765f60f23842450e1151cfd9c89.png)

---

## Opakování - složitost

- $\Omega$ notace ("Omega"): Nechť $f, g:\N→\R$ jsou dvě funkce. Řekneme, že funkce $f(n)$ je třídy $\Omega(g(n))$, jestliže existuje taková kladná reálná konstanta $c$, že existuje nějaké přirozené $n_0$ takové, že pro všechna $n≥n_0$ platí $f(n)\ge c \cdot g(n)$.

$$
  f(n) \in \Omega(g(n)) \iff  \exist c > 0 ~ \exist n_o ~ \forall n \ge n_0: f(n) \ge c \cdot g(n)
  $$

- $\Theta$ notace ("Theta"): Řekneme, že funkce $f(n)$ je třídy $\Theta(g(n))$, jestliže $f(n)$ je jak třídy $\mathcal{O}(g(n))$, tak třídy $\Omega(g(n))$.

![Omega example](imgs/c02e6916d15bacae7a936381af8c6e5a0068f4fd.png)		![Omega example](imgs/2bdc25c7eda8486d05b8031c5a63535684ecb5a1.png)

---

## Příklad 4 ze cvičení 1

### Hledání kuličky

Nepřítel nám dal 9 opticky stejných kovových kuliček a rovnoramenné váhy a prozradil nám, že jedna z kuliček je nepatrně těžší, než ostatní.

- Kolikrát musíme použít váhy, abychom tuto kuličku identifikovali?

- Jaká je odpověď, je-li kuliček 8? Jaká je odpověď, je-li kuliček 10?

- Jaká je odpověď, může-li být odlišná kulička i lehčí? (příklad s *)

---

## Rozbor hvězdiček

Najděte funkci $f(n)$, která určuje počet hvězdiček v závislosti na $n$, najděte funkci $\Theta$, do které tato funkce patří.

_Na vstupu máme číslo `n`_

__Algoritmus 1__
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , n opakujeme:
3.       Vytiskneme *.
```

__Algoritmus 2__
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , i opakujeme:
3.       Vytiskneme *.
```

---

__Algoritmus 1__
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , n opakujeme:
3.       Vytiskneme *.
```

__Algoritmus 2__
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , i opakujeme:
3.       Vytiskneme *.
```

__Algoritmus 3__
```
1. Dokud n ≥ 1, opakujeme:
2.    Vytiskneme *.
3.    n ← Dolní část z n/2.
```

__Algoritmus 4__ (příklad s *)
```
1. Dokud je n > 0, opakujeme:
2.    Je-li n liché:
3.       Pro i = 1, . . . , n opakujeme:
4.          Vytiskneme *.
5.    n ← Dolní část z n/2.
```

---
__Algoritmus 1__
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , n opakujeme:
3.       Vytiskneme *.
```

- vypíšeme $n^2$ hvězdiček

- cca $4n^2$ kroků (změna `i` a `j` , podmínky a vypsání)

- $4n^2 \in \Theta(n^2)$

- Časová složitost $\Theta(n^2)$

- Prostorová složitost $\Theta(1)$

---

__Algoritmus 2__  kroků
```
1. Pro i = 1, . . . , n opakujeme:
2.    Pro j = 1, . . . , i opakujeme:
3.       Vytiskneme *.
```

- vypíšeme $\frac{n (n + 1)}{2}$ hvězdiček

- $\frac{n (n + 1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n$

- cca $2n^2 + 2n$ kroků

- $(\frac{1}{2}n^2 + \frac{1}{2}n) \in \Theta(n^2)$

- Časová složitost $\Theta(n^2)$ a prostorová složitost $\mathcal{O}(1)$

---

__Algoritmus 3__
```
1. Dokud n ≥ 1, opakujeme:
2.    Vytiskneme *.
3.    n ← Dolní část z n/2.
```

- v každém kroku se $n$ sníží na $\lfloor n/2 \rfloor$

- po $k$ krocích je $n_k = \lfloor n/2^k \rfloor$

- hledáme $l$ takové $1 = \lfloor n/2^l \rfloor$

- $l = \log_2(n)$

- vypíšeme $\log_2(n)$ hvězdiček

- cca $4\log_2(n)$ kroků

- $\log_2(n) \in \Theta(\log_2(n))$

- Časová složitost $\Theta(\log_2(n))$ a prostorová složitost $\mathcal{O}(1)$

---

__Algoritmus 4__ (příklad s *)
```
1. Dokud je n > 0, opakujeme:
2.    Je-li n liché:
3.       Pro i = 1, . . . , n opakujeme:
4.          Vytiskneme *.
5.    n ← Dolní část z n/2.
```

- lze dokázat, že počet hvězdiček nebude vyšší než $2n$

- cca $8n$ kroků

- $8n \in \Theta(n)$

Příklady vychází z [Průvodce labyrintem algoritmů, str 43](https://knihy.nic.cz/files/edice/pruvodce_labyrintem_algoritmu.pdf)

---

## Počítání

Dokažte nebo vyvraťte následující tvrzení:

1. Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $g(n) = \mathcal{O}(f(n))$

2. Pro každou trojici funkcí $f_1, f_2, g: \N → \R^{+}$ platí: pokud $f_1(n) = O(g(n))$ a zároveň $f_2(n) = \mathcal{O}(g(n))$, pak $f_1(n) + f_2(n) = \mathcal{O}(g(n))$

3. Pro každou trojici funkcí $f_1, f_2, g: \N → \R^{+}$ platí: pokud $f_1(n) = \mathcal{O}(g(n))$ a zároveň $f_2(n) = \mathcal{O}(g(n))$, pak $f_1(n) * f_2(n) = \mathcal{O}(g(n))$

4. Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $2^{f(n)} = \mathcal{O}(2^{g(n)})$

5. Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $g(n) = \Omega(f(n))$

6. Pro každou funkci $f: \N → \R^{+}$ platí: $f(n) = \mathcal{O}((f(n))^2)$

---

__1.__ Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $g(n) = \mathcal{O}(f(n))$

Neplatí, $n \in \mathcal{O}(n^2)$, ale $n^2 \notin \mathcal{O}(n)$

__2.__ Pro každou trojici funkcí $f_1, f_2, g: \N → \R^{+}$ platí: pokud $f_1(n) = O(g(n))$ a zároveň $f_2(n) = \mathcal{O}(g(n))$, pak $f_1(n) + f_2(n) = \mathcal{O}(g(n))$

Platí, dosadím do definice: $f_1(n) \ge c_1 \cdot g(n) \land f_2(n) \ge c_2 \cdot g(n) \implies f_1(n) + f_2(n) \ge (c_1 + c_2) \cdot g(n)$

__3.__ Pro každou trojici funkcí $f_1, f_2, g: \N → \R^{+}$ platí: pokud $f_1(n) = \mathcal{O}(g(n))$ a zároveň $f_2(n) = \mathcal{O}(g(n))$, pak $f_1(n) * f_2(n) = \mathcal{O}(g(n))$

Neplatí, $n^2 \in \mathcal{O}(n^2)$ a $n \in \mathcal{O}(n^2)$, ale $n^3 \notin \mathcal{O}(n^2)$

__4.__ Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $2^{f(n)} = \mathcal{O}(2^{g(n)})$

Neplatí, uvažme $f(n)=2\log_2 n \land g(n)=\log_2 n$, potom platí, že $f(n) = \mathcal{O}(g(n))$, ale $2^{f(n)} = 2^{2 \log_2 n} = (2^{\log_2 n})^2 = n^2$ a $2^{g(n)} = 2^{\log_2 n} = n$ a ty nesplňují $2^{f(n)} = \mathcal{O}(2^{g(n)})$.
Pozn. $a^{xy} = (a^x)^y$

---

__5.__ Pro každou dvojici funkcí $f, g: \N → \R^{+}$ platí: pokud $f(n) = \mathcal{O}(g(n))$, pak $g(n) = \Omega(f(n))$

Platí, dosadím do definice: $f(n) \le c \cdot g(n) \land c > 0 \implies \frac{1}{c} f(n) \le g(n) \implies g(n) \ge \frac{1}{c} f(n)$

__6.__ Pro každou funkci $f: \N → \R^{+}$ platí: $f(n) = \mathcal{O}((f(n))^2)$

Neplatí, pro $f(n) = 1/n$ dostaneme $\frac{1}{n} \notin \mathcal{O}(\frac{1}{n^2})$ (protože $1 \le c \cdot \frac{1}{n}$)

---

## Příklady na příště / na konec

1. Posloupnost N čísel – maximum a počet jeho výskytů

2. Posloupnost N čísel – maximální číslo bez opakování

3. Posloupnost N čísel – číslo s maximálním počtem výskytů

---

## Zdroje:

- [Průvodce labyrintem algoritmů, Kapitola 2.4](https://knihy.nic.cz/files/edice/pruvodce_labyrintem_algoritmu.pdf)

- [Khan Academy, Asymptotic notation](https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation)