Vino (DomJudge)¶

38 akceptovaných riešení

Chyby¶

pažravý prístup
3-rozmerné pole pre memoizáciu/dynamické programovanie [MEMORY LIMIT]

jazyk	počet	čas
Java	32	`1,91` - `8,75`
C++	6	`0,41` - `7,16`<

Násobenie matíc¶

Násobenie dvoch matíc $A \cdot B = C$

Rozmery matíc $A...a \times b, B ... b \times c, C ... a \times c$.

Prvok výslednej matice je skalárny súčin riadku prvej a stĺpca druhej matice

$$ c_{ij} = \sum_{k=1}^{b} a_{ik} \cdot b_{kj}$$

$\Theta(a \cdot c \cdot b)$ - pre všetky prvky výslednej matice musíme vypočítať danú sumu.

Štvorcové matice (s rozmerom $2^n$)¶

$$ A \cdot B = C$$

priamočiaro rozdeľuj a panuj

teda 8 násobení a 4 sčítaní $T(n) = 8 \cdot T\left(\frac{n}{2}\right)+4 \cdot \frac{n^2}{4}$

$T(n) \in O\left(n^3\right)$

Strassenov algoritmus pre štvorcové matice `1969`¶

https://link.springer.com/article/10.1007/BF02165411

len 7 násobení a 18 sčítaní $T(n) = 7 \cdot T\left(\frac{n}{2}\right)+18 \cdot \frac{n^2}{4}$

$T(n) \in O\left(n^{log_2 7}\right) = O\left(n^{2.80735492206}\right)$

In [2]:

from math import log
log(7, 2)

Out[2]:

2.807354922057604

ďalšie vylepšienia https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

Algoritmy usporiadania `Sorting algorithms`¶

Ako by ste si zoradili karty počas hry UNO?

Algoritmy usporiadania `Sorting algorithms`¶

`BogoSort`¶

deterministická verzia, skúšame všetky permutácie či sú utriedené $O(n \cdot n!) = O\left((n+1)!\right)$

randomizovaná verzia (náhodná permutácia+kontrola usporiadanosti), môže byť nekonečná

Existujú aj menej efektívne:

Miguel A. Lerma: How inefficient can a sort algorithm be?

https://arxiv.org/abs/1406.1077

`StoogeSort`¶

vymeň krajné prvky pole[0], pole[-1] (ak sú v nesprávnom poradí)
usporiadaj (rekurzívne) prvé dve tretiny
usporiadaj druhé dve tretiny
usporiadaj znova prvé dve tretiny

https://www.youtube.com/watch?v=bfzYj-qGw7U

$T(n) = 3*T\left(\frac{2}{3}n\right)+1$

$O\left(n^{log_{1.5} 3}\right)$

In [6]:

from math import log
log(3, 1.5)

Out[6]:

2.709511291351455

$O\left(n^{log_{1.5} 3}\right) \approx O(n^{2.70951})$

Bublinkové usporiadanie `BubbleSort`¶

$O(n^2)$
pri každej iterácii maximum prebuble napravo/na koniec

In [15]:

for i in range(len(pole)-1):
    for j in range(len(pole)-1):
        if pole[j] > pole[j+1]:
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena susednych prvkov

In [17]:

for i in range(len(pole)-1):
    for j in range(len(pole)-1-i): # posledne prvky uz nemusime kontrolovat
        if pole[j] > pole[j+1]:
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena susednych prvkov

najhorší prípad je opačne usporiadaná postupnosť, dokonca stačí, že minimum je na konci
skončíme, ak sa vnútri cyklu i nevymenili žiadne dva prvky (už je usporiadané)

In [49]:

for i in range(len(pole)-1):
    bez_vymeny =  True
    for j in range(len(pole)-1-i): # posledne prvky uz nemusime kontrolovat
        if pole[j] > pole[j+1]:
            pole[j], pole[j+1] = pole[j+1], pole[j] #vymena susednych prvkov
            bez_vymeny = False
    if bez_vymeny:
        break

Koktejlové usporiadanie `CoctailSort` `ShakerSort`¶

bublinkové na striedačku dvoma smermi (max -> / min <- )

stále kvadratické riešenie

Usporiadanie výberom `SelectionSort`¶

vyberieme minimum, teda nájdeme jeho index a vymeníme s prvým prvkom (pokračuje od druhého prvku)
$O(n^2)$ vždy (bez ohľadu na hodnoty v postupnosti)
počet výmen je v najhoršom prípade $O(n)$

In [39]:

for index in range(len(pole)-1):
    min_ind = index
    for index2 in range(index+1, len(pole)):
        if pole[min_ind] > pole[index2]:
            min_ind = index2
    pole[min_ind], pole[index] = pole[index], pole[min_ind]

Usporiadanie vkladaním `InsertSort`¶

máme usporiadanú postupnosť (časť) a pridáme/vložíme ďalší prvok na správne miesto
nový prvok prebuble doľava (smerom k začiatku)
$O(n^2)$ v prípade opačne usporiadanej postupnosti, najrýchlejšie $O(n)$ v prípade už usporiadanej postupnosti

In [42]:

for index in range(1, len(pole)):
    hodnota = pole[index]
    pozicia = index-1
    while pozicia >= 0 and pole[pozicia] > hodnota:
        pole[pozicia+1] = pole[pozicia]
        pozicia -= 1
    pole[pozicia+1] = hodnota

Usporiadanie spájaním `MergeSort`¶

rozdeľuj a panuj

$$T(n) = T\left(\left\lceil \frac{n}{2} \right\rceil\right) + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +O(n) $$$$T(n) = 2 \cdot T\left(\frac{n}{2}\right)+O(n)$$$$O\left(n \log n\right)$$

In [45]:

def usporiadanie_spajanim(pole):
    if len(pole) < 2:
        return pole
    stred = len(pole)//2
    usp_lava = usporiadanie_spajanim(pole[:stred])
    usp_prava = usporiadanie_spajanim(pole[stred:])
    vysl = []
    while len(usp_lava) > 0 and len(usp_prava) > 0:
        vysl.append(usp_lava.pop(0) if usp_lava[0]  <= usp_prava[0] else usp_prava.pop(0) )
    vysl.extend(usp_lava+usp_prava)
    return vysl

Usporiadanie haldovaním `HeapSort`¶

vytvorenie max-haldy

postupne vkladáme po jednom prvku do haldy

vloženie prvku má logaritmickú zložitosť

$O(n \cdot \log n)$, teda presnejšie $O(\log 1+\log 2+\dots+\log n) = O(\log n!)$

postupne vyberáme max z haldy a dáme na koniec (stále v tom istom poli)

výber je zase v logaritmickom čase $O(\log n+\log (n-1)+\cdots+\log 1)$

Celková časová zložitosť je $O(n \cdot \log n)$

Haldu vieme vytvoriť aj v lineárnom čase $O(n)$ heapify. Postupne od konca vždy rodiča prebublememe nadol $O(\log 1 + \cdots + \log 1 + \log 3+\cdots+\log 3+\log 7+ \cdots+ \log n) = O(n)$

Rýchle usporiadanie `QuickSort`¶

výber pivota, rozdelenie na prvky menšie a väčšie

pri správnom výbere pivota je $T(n) = 2.T\left(\frac{n}{2}\right)+O(n)$, teda $O(n \cdot \log n)$

pri nesprávnom výbere to môže byť $T(n) = T(0)+T(n-1)+O(n)$, teda $O(n^2)$

pri výber prvého alebo posledného prvku najhoršia možnosť nastáva v prípade, ak pole je už usporiadané

http://videolectures.net/mit6046jf05_leiserson_lec04/

v praxi rôzne vylepšenia

medián z troch prvkov (prvý, prostredný a posledný)
randomizovaný quicksort
pri malom počte prvkov prepnúť na InsertSort, pri veľkom počte rekurzíí zase na MergeSort

3-cestná randomizovaná verzia v Pythone

In [22]:

from random import choice, randrange

def rychle_usporiadanie(pole):
    if len(pole) < 2:
        return pole
    pivot = choice(pole)
    return rychle_usporiadanie([prvok for prvok in pole if prvok < pivot]) + \
           [prvok for prvok in pole if prvok == pivot] + \
           rychle_usporiadanie([prvok for prvok in pole if prvok > pivot])

In [23]:

print(*rychle_usporiadanie([randrange(10, 100) for _ in range(30)]))

10 10 14 15 15 19 20 23 23 27 32 34 35 38 39 41 46 52 53 59 68 70 74 84 85 86 91 92 93 94

Ďalšie algoritmy¶

`SmoothSort

Dijkstra: Smoothsort - an alternative for sorting in situ, 1981

http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

LibrarySort

Bender/Farach-Colton/Mosteiro: INSERTION SORT is O (n log n), 2006

https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaMo06-librarysort.pdf

Vlastnosti algoritmov usporiadania¶

počet porovnaní = časová zložitosť v najhoršom prípade (najlepšom, priemernom)
počet výmen
"na mieste"/in-place/situ ak pamäťová zložitosť je $O(\log n)$
stabilita (prvky s rovnakou hodnotu zostanú v rovnakom poradí alebo nemusia)

Odkazy¶

https://www.youtube.com/watch?v=GIvjJwzrHBU (Listening to Sorting Algorithms!)

https://www.toptal.com/developers/sorting-algorithms (Sorting Algorithms Animations)

https://imgur.com/gallery/voutF (Sorting Algorithms Visualized)

https://sortvisualizer.com/ (Sort Visualizer)

Dolný odhad zložitosti porovnávacích algoritmov usporiadania¶

$$ T(n) \in \Omega(n \log n)$$

linearithmic time

Porovnávacie algoritmy usporiadania vieme zapísať vo forme rozhodovacích stromov, pre každé porovnanie sú dve možnosti, teda dvaja potomkovia.

Majme 3 prvky a, b, c.

.	.	.	.	.	.	.	.	.	.	.
					a<b
			a<c				c<b
	b<c			c,a,b		c,b,a			a<c
a,b,c		a,c,b						b,a,c		b,c,a

Každý porovnávací algoritmus vieme zapísať v takomto rozhodovacom strome ... časová zložitosť, teda najhorší počeť porovnaní je dĺžka najdlhšej cesty z koreňa (vrchného prvku) k listu.

Pre 3 prvky sú potrebné najviac 3 porovnania. Pre dve porovnania máme len 4 možnosti v ktorých môžeme skončiť, a teda nemôže byť takýto algoritmus usporiadania správny, lebo pre 3 prvky máme až šesť možností (permutácií).

Ak máme počet prvkov $n$, tak počet permutácií je $n!$. Počet listov v binárnom strome je nanajvýš $2^h$, kde $h$ je hĺbka-výška stromu.

Musí teda platiť $$ n! \le 2^h $$

$$ \log_2 n! \le h $$

$$ \log_2 n+ \log_2 (n-1)+\dots+\log_2 \frac{n}{2}+\log_2 \frac{n-2}{2}+\dots+\log_2 2+\log_2 1 \le h $$

$$ \log_2 \frac{n}{2}+ \dots + \log_2 \frac{n}{2}+0+\dots+0 \le h $$

$$ \frac{n}{2} \cdot \log_2 \frac{n}{2} \le h $$

teda $h \in \Omega(n \cdot \log n)$

In [ ]:

Vino (DomJudge)¶

Chyby¶

Násobenie matíc¶

Štvorcové matice (s rozmerom $2^n$)¶

Strassenov algoritmus pre štvorcové matice 1969¶

Algoritmy usporiadania Sorting algorithms¶

Algoritmy usporiadania Sorting algorithms¶

BogoSort¶

StoogeSort¶

Bublinkové usporiadanie BubbleSort¶

Koktejlové usporiadanie CoctailSort ShakerSort¶

Usporiadanie výberom SelectionSort¶

Usporiadanie vkladaním InsertSort¶

Usporiadanie spájaním MergeSort¶

Usporiadanie haldovaním HeapSort¶

Rýchle usporiadanie QuickSort¶

Ďalšie algoritmy¶

Vlastnosti algoritmov usporiadania¶

Odkazy¶

Dolný odhad zložitosti porovnávacích algoritmov usporiadania¶

Strassenov algoritmus pre štvorcové matice `1969`¶

Algoritmy usporiadania `Sorting algorithms`¶

Algoritmy usporiadania `Sorting algorithms`¶

`BogoSort`¶

`StoogeSort`¶

Bublinkové usporiadanie `BubbleSort`¶

Koktejlové usporiadanie `CoctailSort` `ShakerSort`¶

Usporiadanie výberom `SelectionSort`¶

Usporiadanie vkladaním `InsertSort`¶

Usporiadanie spájaním `MergeSort`¶

Usporiadanie haldovaním `HeapSort`¶

Rýchle usporiadanie `QuickSort`¶