12 akceptovaných riešení
greedy
... WRONG ANSWER
brute force
... TIMELIMIT
dynamic programming
so stavom [rok, vlavo, vpravo] ... MEMORYLIMIT
memoizácia v Pythone .., RUNERROR
RecursionError: maximum recursion depth exceeded in comparison
https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
jazyk | počet | čas | kód (riadky / znaky) |
---|---|---|---|
Java | 10 | 2,66 - 8,61 |
40-160 / 1078-3966 |
C | 1 | 3,36 |
43 / 932 |
C++ | 1 | 3,58 |
36 / 821 |
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.
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)$
1969
¶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)$
from math import log
log(7, 2)
2.807354922057604
Matrix Chain Multiplication
¶$ (A \cdot B) \cdot C = (A \cdot B)_{2x3} \cdot C_{3x9}$ znamená $2 \cdot 7 \cdot 3 + 2 \cdot 3 \cdot 9 = 96$ násobení
$ A \cdot (B \cdot C) = A_{2x7} \cdot (B \cdot C)_{7x9}$ znamená $7 \cdot 3 \cdot 9 + 2 \cdot 7 \cdot 9 = 315$ násobení
dynamické programovanie na určenie minimálneho počtu násobení
štandardne môžeme dvojrozmerné DP počítať po riadkoch, sĺpcoch, uhlopriečkach (dvoma smermi aj zigzag)
tu potrebujeme súvislé úseky dvoch, troch, štyroch, ... matíc
Sorting algorithms
¶BogoSort
¶Existujú aj menej efektívne:
Miguel A. Lerma: How inefficient can a sort algorithm be?
StoogeSort
¶$T(n) = 3*T\left(\frac{2}{3}n\right)+1$
$O\left(n^{log_{1.5} 3}\right)$
from math import log
log(3, 1.5)
2.709511291351455
$O\left(n^{log_{1.5} 3}\right) \approx O(n^{2.70951})$
BubbleSort
¶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
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
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
CoctailSort
ShakerSort
¶SelectionSort
¶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]
InsertSort
¶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
MergeSort
¶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
HeapSort
¶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!)$
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)$
QuickSort
¶v praxi rôzne vylepšenia
3-cestná randomizovaná verzia v Pythone
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])
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
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
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)
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 $$
teda $h \in \Omega(n \cdot \log n)$