Vyhledávání, řazení, složitost
IB111 Úvod do programování skrze Python
2012
Otrávené studny
8 studen, jedna z nich je otrávená
laboratorní rozbor
dokáže rozpoznat přítomnost jedu ve vodě
je drahý
(je časově náročný)
kolik rozborů (času) potřebujeme?
jak určit otrávenou studnu?
Otrávené studny: řešení
Řešení s využití binárních čísel
studna kód studna kód
A 000 E 100
B 001 F 101
C 010 G 110
D 011 H 111
test přidělené studny
1 B, D, F, H
2 C, D, G, H
3 E, F, G, H
Vyhledávání: hra
Myslím si přirozené číslo X mezi 1 a 1000.
Povolená otázka: „Je X menší než N?
Kolik otázek potřebujete na odhalení čísla?
Kolik předem formulovaných otázek potřebujete?
Mezi kolika čísly jste schopni odhalit skryté číslo na K
otázek?
Vyhledávání: řešení
„dynamické otázky : půlení intervalu
„předem formulované otázky : dotazy na bity v bitovém
zápisu (stejně jako u studen)
N čísel: potřebujeme log2 N otázek
K otázek: rozlišíme mezi 2K
čísly
Připomenutí: logaritmus
x = by
⇔ y = logb(x)
log10(1000) = 3
log2(16) = 4
log2(1024) = 10
logb(xy) = logb(x) + logb(y)
log3(81) = ?
log2(2) = ?
log10(0.1) = ?
http://www.khanacademy.org/math/algebra/logarithms
http://khanovaskola.cz/logaritmy/uvod-do-logaritmu
Vyhledávání: motivace
vyhledávání v (připravených) datech je velmi častý problém:
web
slovník
informační systémy
dílčí krok v algoritmech
Vyhledávání: konkrétní problém
vstup: seřazená posloupnost čísel + dotaz (číslo)
např. 2, 3, 7, 8, 9, 14 + dotaz 8
výstup: index hledaného čísla v posloupnosti (případně -1
pokud tam není)
výsledek příkladu: 3 (číslování od nuly)
Vyhledávání a logaritmus
naivní metoda = průchod seznamu
lineární vyhledávání, O(n)
pomalé (viz např. databáze s milióny záznamů)
jen velmi krátké seznamy
základní rozumná metoda = půlení intervalu
logaritmický počet kroků (vzhledem k délce seznamu),
O(log(n))
Vyhledávání: půlení intervalu
binární vyhledávání
podobné jako: hra s hádáním čísel, aproximace odmocniny
podíváme se na prostřední člen ⇒ podle jeho hodnoty
pokračujeme v levém/pravém intervalu
udržujeme si „horní mez a „spodní mez
Vyhledávání: program
def binarni_vyhledavani(hodnota, seznam):
spodni_mez = 0
horni_mez = len(seznam) - 1
while spodni_mez <= horni_mez:
stred = (spodni_mez + horni_mez) / 2
if seznam[stred] == hodnota:
return True
elif seznam[stred] > hodnota:
horni_mez = stred - 1
else:
spodni_mez = stred + 1
return False
Vyhledávání: rekurzivní varianta
def binarni_vyhledavani(hodnota, seznam,
spodni_mez, horni_mez):
if spodni_mez > horni_mez:
return False
stred = (spodni_mez + horni_mez)/2
if seznam[stred] < hodnota:
return binarni_vyhledavani(hodnota, seznam,
stred+1, horni_mez)
elif seznam[stred] > hodnota:
return binarni_vyhledavani(hodnota, seznam,
podni_mez, stred-1)
else:
return True
Vyhledávání, přidávání, ubírání
seřazený seznam – rychlé vyhledávání, ale pomalé
přidávání prvků
rychlé vyhledávání, přidávání i ubírání prvků – datová
struktura slovník; vyhledávací stromy, hašovací tabulky
více později / v IB002
Řadicí algoritmy: terminologická poznámka
anglicky „sorting algorithm
česky používáno: řadicí algoritmy nebo třídicí algoritmy
řadicí vesměs považováno za „správnější
Řadicí algoritmy: komentář
mnoho různých algoritmů pro stejný účel
většina programovacích jazyků má vestavěnou podporu
(funkce sort())
Proč se tím tedy zabýváme?
Řadicí algoritmy: komentář
Proč se tím tedy zabýváme?
1 ukázka programů se seznamy
2 ilustrace algoritmického myšlení, technik návrhu algoritmů
3 typický příklad drobné změny algoritmu s velkým
dopadem na rychlost programu
4 hezky se to vizualizuje a vysvětluje
5 tradice, patří to ke vzdělání informatika
6 občas se to může i hodit
Doporučený zdroj
http://www.sorting-algorithms.com/
animace
kódy
vizualizace
Více podobných: Google → sorting algorithms
A na zpestření: http://www.youtube.com/watch?v=lyZQPjUT5B4
Řadicí algoritmy: problém
vstup: posloupnost (přirozených) čísel
např. 8, 2, 14, 3, 7, 9
výstup: seřazená posloupnost
např. 2, 3, 7, 8, 9, 14
Pokus č. 1
zkoušíme systematicky všechna možná uspořádání prvků
pro každé z nich ověříme, zda jsou prvky korektně
uspořádány
je to dobrý algoritmus?
Co vy na to?
zkuste vymyslet
řadicí algoritmus
co nejvíce různých principů
co nejefektivnější algoritmus
možná inspirace: jak řadíte karty?
Složitost
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
), „kvadratická
složitější algoritmy O(n log(n))
Bublinkové řazení (Bubble sort)
„probublávání vyšších hodnot nahoru
srovnávání a prohazování sousedů
po i iteracích je nejvyšších i členů na svém místě
Bublinkové řazení: program
def bublinkove_razeni(a):
n = len(a)
for i in range(n):
for j in range(n-i-1):
if a[j] > a[j+1]:
tmp = a[j]
a[j] = a[j+1]
a[j+1] = tmp
invariant cyklu: a[n-i-1:] ve finální pozici
Bublinkové řazení: příklad běhu
[8, 2, 7, 14, 3, 1]
[2, 7, 8, 3, 1, 14]
[2, 7, 3, 1, 8, 14]
[2, 3, 1, 7, 8, 14]
[2, 1, 3, 7, 8, 14]
[1, 2, 3, 7, 8, 14]
Řazení výběrem (Select sort)
řazení výběrem
projdeme dosud neseřazenou část pole a vybereme
nejmenší prvek
nejmenší prvek zařadíme na aktuální pozici (výměnou)
Řazení výběrem: program
def razeni_vyberem(a):
for i in range(len(a)):
vybrany = i
for j in range(i+1, len(a)):
if a[j] < a[vybrany]: vybrany = j
tmp = a[i]
a[i] = a[vybrany]
a[vybrany] = tmp
Řazení vkládáním (Insert sort)
podobně jako „řazení karet
prefix pole udržujeme seřazený
každou další hodnotu zařadíme tam, kam patří
Řazení vkládáním: program
def razeni_vkladanim(a):
for i in range(1,len(a)):
aktualni = a[i]
j = i
while j > 0 and a[j-1] > aktualni:
a[j] = a[j-1]
j -= 1
a[j] = aktualni
Quicksort
rekurzivní algoritmus
vybereme „pivota a pole rozdělíme na dvě části:
větší než pivot
menší než pivot
obě části pak nezávisle seřadíme (rekurzivně pomocí
quicksortu)
Quick sort ilustrace
Quick sort
pokud máme smůlu při výběru pivota, tak je stejně
pomalý jako předchozí
v průměrném případě je rychlý – quick
O(n log(n))
Řazení slučováním (Merge sort)
rekurzivní algoritmus
pole rozdělíme na dvě poloviny a ty seřadíme (pomocí
Merge sort)
ze seřazených polovin vyrobíme jedno seřazené pole –
„zipování
vždy efektivní – O(n log(n))
Radix sort
předchozí algoritmy využívají pouze operaci porovnání
dvou hodnot
aplikovatelné na cokoliv, co lze porovnávat, žádné další
předpoklady
s doplňujícími předpoklady můžeme dostat nové algoritmy
(obecný princip)
Radix sort
aplikovatelné na (krátká) čísla
postupujeme od nejméně významné cifry k nejvýznamnější
seřadíme pole podle dané cifry = rozdělení do 10
„kyblíčků (jednoduché, rychlé)
Radix sort ilustrace
Složitost trochu podrobněji
složitost algoritmu – jak je algoritmus výpočetně náročný
časová, prostorová
měříme počet operací nikoliv čas na konkrétním stroji
vyjadřujeme jako funkci délky vstupu
O notace – zanedbáváme konstanty
např. O(n), O(n log(n)), O(n2
)
Ilustrace rozdílů v složitosti
Složitost řadicích algoritmů
n – délka vstupní posloupnosti
počet operací
jednoduché algoritmy O(n2
), „kvadratická
složitější algoritmy O(n log(n))
Shrnutí
vyhledávání: půlení intervalu, rekurze
řadicí algoritmy:
jednoduché (kvadratické): bublinkové, výběrem,
vkládáním
složitější (n log n, rekurzivní): quick sort, slučování