---
tags: vaje, or, zahtevnost
hackmd: https://hackmd.io/-RcUkD_uS3qZEme5cvkOmw
plugins: mathjax, mermaid
---
# Operacijske raziskave - vaje 22.2.2021

---

## Zahtevnost algoritmov

* $f \in O(g) \iff \exists C > 0 \ \exists {n_0} \ \forall n \ge {n_0} : \vert f(n) \vert \le C g(n)$ asimptotična zgornja meja
* $f \in \Omega(g) \iff \exists C > 0 \ \exists {n_0} \ \forall n \ge {n_0} : \vert f(n) \vert \ge C g(n)$ asimptotična spodnja meja
* $f \in \Theta(g) \iff f \in O(g) \cap \Omega(g)$ asimptotična natančna meja
* $f(n) = O(g(n))$

---

### Naloga 1

Naj bo $A[1 \dots n][1 \dots n]$ matrika (tj., seznam seznamov) dimenzij $n \times n$. Dan je spodnji program:

for i = 1, ..., n:
    for j = i+1, ..., n:
        A[i][j] <- A[j][i]

1. Kaj počne zgornji program?
2. Oceni število korakov, ki jih opravi zgornji program, v odvisnosti od parametra $n$.

----

1. Program preslika del matrike pod diagonalo v del nad diagonalo, tako da je matrika $A$ na koncu simetrična.
2. ${\sum_{i=1}^n} {\sum_{j=i+1}^n} 1 = {\sum_{i=1}^n} (n-i) = {\sum_{i=0}^{n-1}} i = {n (n-1) \over 2} = \Theta(n^2)$

---

### Naloga 2

Naj bo $\ell[1 \dots n]$ seznam, ki ima na začetku vse vrednosti nastavljene na $0$. Dan je spodnji program:

i <- 1
while i <= n:
    l[i] <- 1 - l[i]
    if l[i] = 1:
        i <- 1
    else:
        i <- i+1

1. Kaj se dogaja, ko teče zgornji program?
2. Oceni število korakov, ki jih opravi zgornji program, v odvisnosti od parametra $n$.

----

| korak | $\ell[4 \dots 1]$ | $i$ | vrednost |
| ----- | ----------------- | --- | -------- |
| 0 | 0, 0, 0, 0 | 1 | 0
| 1 | 0, 0, 0, 1 | 1 | 1
| 2 | 0, 0, 0, 0 | 2 |
| 3 | 0, 0, 1, 0 | 1 | 2
| 4 | 0, 0, 1, 1 | 1 | 3
| 5 | 0, 0, 1, 0 | 2 |
| 6 | 0, 0, 0, 0 | 3 |
| 7 | 0, 1, 0, 0 | 1 | 4

1. Algoritem simulira $n$-bitni števec.
2. ${\sum_{i=0}^{n-1}} 2^{n-i} = {\sum_{i=1}^n} 2^i = 2^{n+1} - 2 = O(2^n)$

---

### Naloga 3

Algoritem `BubbleSort` uredi vhodni seznam $\ell[1 \dots n]$ tako,
da zamenjuje sosednje elemente v nepravem vrstnem redu:

def BubbleSort(l[1, ..., n]):
    z <- n
    while z > 1:
        y <- 1
        for i = 2, ..., z:
            if l[i-1] > l[i]:
                l[i-1], l[i] <- l[i], l[i-1]
                y <- i
        z <- y-1

1. Izvedi algoritem na seznamu $[7, 11, 16, 7, 5]$.
2. Določi časovno zahtevnost algoritma.

----

| $z$ | $y$ | $i$ | $\ell$ |
| --- | --- | --- | ------ |
| 5 | 1 | 2 | 7, 11, 16, 7, 5
| 5 | 1 | 3 | 7, 11, 16, 7, 5
| 5 | 4 | 4 | 7, 11, 7, 16, 5
| 5 | 5 | 5 | 7, 11, 7, 5, 16
| 4 | 1 | 2 | 7, 11, 7, 5, 16
| 4 | 3 | 3 | 7, 7, 11, 5, 16
| 4 | 4 | 4 | 7, 7, 5, 11, 16
| 3 | 1 | 2 | 7, 7, 5, 11, 16
| 3 | 3 | 3 | 7, 5, 7, 11, 16
| 2 | 2 | 2 | 5, 7, 7, 11, 16

* Časovna zahtevnost (najslabši primer - obratno urejen seznam): $O(n^2)$
* Najboljši primer (urejen seznam): $\Omega(n)$

---

### Naloga 4

Algoritem `MergeSort` uredi vhodni seznam tako, da ga najprej razdeli na dva dela, nato vsakega rekurzivno uredi, nazadnje pa zlije dobljena urejena seznama.

1. S psevdokodo zapiši algoritem `MergeSort`.
2. Izvedi algoritem na seznamu $[7, 11, 16, 7, 5, 0, 14, 1, 19, 13]$.
3. Določi časovno zahtevnost algoritma.

----

def MergeSort(l[1, ..., n]):
    if n <= 1:
        return l
    m <- n // 2 # zaokrožimo navzdol
    l1 <- MergeSort(l[1, ..., m])
    l2 <- MergeSort(l[m+1, ..., n])
    i, j, k <- 1, 1, 1
    while j <= m and k <= n-m:
        if l1[j] <= l2[k]:
            l[i] <- l1[j]
            j <- j+1
        else:
            l[i] <- l2[k]
            k <- k+1
        i <- i+1
    while j <= m:
        l[i] <- l1[j]
        j <- j+1
        i <- i+1
    while k <= n-m:
        l[i] <- l2[k]
        k <- k+1
        i <- i+1
    return l
    

graph TD

a[7, 11, 16, 7, 5, 0, 14, 1, 19, 13]
a --- b[7, 11, 16, 7, 5]
a --- c[0, 14, 1, 19, 13]
b --- d[7, 11]
b --- e[16, 7, 5]
d --- f[7]
d --- g[11]
f --- h[7, 11]
g --- h
e --- i[16]
e --- j[7, 5]
j --- k[7]
j --- l[5]
k --- m[5, 7]
l --- m
i --- n[5, 7, 16]
m --- n
h --- o[5, 7, 7, 11, 16]
n --- o
c --- p[0, 14]
c --- q[1, 19, 13]
p --- r[0]
p --- s[14]
r --- t[0, 14]
s --- t
q --- u[1]
q --- v[19, 13]
v --- w[19]
v --- x[13]
w --- y[13, 19]
x --- y
u --- z[1, 13, 19]
y --- z
t --- A[0, 1, 13, 14, 19]
z --- A
o --- B[0, 1, 5, 7, 7, 11, 13, 14, 16, 19]
A --- B

Krovni izrek:

$$
T(n) = a T\left({n \over b}\right) + O(n^c) = O\left({\sum_{i=0}^{ {\log_b} n}} \left({a \over b^c}\right)^i n^c\right) = \begin{cases}
O(n^c) & a < b^c \\
O(n^c \log n) & a = b^c \\
O(n^{\log_b a}) & a > b^c
\end{cases}
$$

`MergeSort`:
* $a = b = 2$, $c = 1$
* $a = b^c$
* časovna zahtevnost: $O(n \log n)$

---

### Naloga 5

Število $n$ želimo razcepiti na dva netrivialna celoštevilska faktorja, kar storimo s sledečim algoritmom:

def Razcep(n):
    for i = 2, ..., [sqrt(n)]: # koren n, zaokrožen navzdol
        if n/i je celo število:
            return (i, n/i)
    return n je praštevilo

Določi časovno zahtevnost algoritma. Ali je ta algoritem polinomski?

---

### Naloga 6

Zapiši rekurziven algoritem, ki na vhod dobi celo število $n$ in teče v času $O(\sqrt{n})$. Uporaba korenjenja ni dovoljena.