C2142 Návrh algoritmů pro přírodovědce
2. Úvod do složitosti
Tomáš Raček
Jaro 2015
Hledání nejčastějších slov – FrequentWords
Zadání. Nalezněte v textu řetězce délky k s nejvyšším počtem
výskytů.
FrequentWords(text, k)
1. Pro každý podřetězec délky k řetězce text spočítej jeho výskyt
pomocí funkce PatternCount(text, pattern)
2. Urči nejvyšší nalezenou četnost
3. Vrať řetězce s touto nejvyšší četností
Praktický test.
• krátké řetězce – FrequentWords uspokojivě funguje
• dlouhé řetězce – nepoužitelné, čas výpočtu neodpovídá odhadu
FrequentWords – doba výpočtu
Pozorování
• doba výpočtu je úměrná velikosti vstupních dat
• závislost není nutně lineární – výpočet na 1000krát větší úloze
nemusí trvat 1000krát déle
• na různých strojích/architekturách různé časy výpočtu
• Thinkpad T430s: 7 s
• Thinkpad X200s: 14 s
Důsledek (1). Nutná hlubší analýza FrequentWords.
Důsledek (2). Porovnání náročnosti algoritmů podle času výpočtu
není vhodné, potřebujeme aparát nezávislý na konkrétním
stroji/architektuře.
Složitost
Složitost algoritmu. Zaveďme složitost algoritmu jako funkci f(n),
kde n je velikost vstupu.
Návrh. f(n) určuje počet jednoduchých operací daného algoritmu
pro vyřešení problému o velikosti n.
• jednoduché operace ≈ instrukce CPU (např. sečtení nebo
porovnání dvou čísel, AND/OR,…)
• řešení nezávislé na architektuře
Důsledek. Porovnání efektivity algoritmů lze zjednodušeně převést
na porovnání jejich složitostí.
Asymptotická složitost – definice
Formální definice
O(g) = { f | ∃c ∈ R+
, ∃n0 ∈ N : ∀n ≥ n0 : 0 ≤ f(n) ≤ c · g(n)}
f ∈ O(g) čteme „ f roste asymptoticky nejvýše tak rychle jako g“.
Význam konstant
c rozdíl pouze v multiplikativní konstantě nepovažujeme za
významný, tj. ztotožňujeme např. n2 a 4n2
n0 uvažujeme pouze „velká“ n
Poznámka. Analogicky lze definovat další množiny:
• f ∈ Ω(g) – f roste asymptoticky alespoň tak rychle jako g
• f ∈ Θ(g) – f roste asymptoticky právě tak rychle jako g
Asymptotická složitost – příklady
Rychlost růstu funkcí
log n ≪ n ≪ n log n ≪ n2
≪ 2n
≪ n! pro n → ∞
Příklady
Funkce Složitostní třída Pojmenování
2142 O(1) konstantní
2 log n + 4 O(log n) logaritmická
0.5n + log n O(n) lineární
n2 − 10n O(n2) kvadratická
6n3 O(n3) kubická
2n − 1 O(2n) exponenciální
Poznámka. Ověření, zdali f ∈ O(g), lze provést výpočtem limity
limn→∞ f(n)/g(n).
Složitost problému
Cíl. Snaha o nalezení efektivních algoritmů pro daný problém.
Otázka. Lze zrychlovat pořád, nebo existuje nějaký dolní limit?
Složitost problému
• minimální počet operací potřebný pro vyřešení libovolné
instance problému
• nutno odvodit teoreticky → mnohdy netriviální
• odpovídá složitosti optimálního algoritmu pro daný problém
Jak ale poznám optimální algoritmus? Srovnejme odhady složitosti
problému Pi a složitosti algoritmů Aj pro tento problém:
P1(n) < . . . < Pk(n) ≤ A1(n) < . . . < Am(n)
A je optimální algoritmus, pokud A(n) = P(n).
Složitost problému – příklady
Nalezení nejmenšího prvku pole
• je nutné projít všechny prvky pole – Ω(n) operací
• algoritmus se složitostí O(n) jistě existuje → složitost problému
(= složitost optimálního algoritmu) je lineární
Násobení matic
• potřeba Ω(n2) operací
• naivní algoritmus – O(n3)
• Strassenův algoritmus – O(nlog2 7) O(n2,81)
• aktuálně nejlepší algoritmus (2014) – O(n2,372...)
• nalezení optimálního algoritmu je otevřený problém
Prostorová složitost
Prostorová složitost. Vedle časové náročnosti algoritmů lze určit i
množství paměti, které algoritmus potřebuje pro svůj výpočet.
• velikost vstupních (a výstupních) dat neuvažujeme
• vyjadřujeme také O-notací
In situ algoritmus vyžaduje navíc pouze O(1) paměti.
• výpočet průměrné hodnoty prvků v poli
• naivní násobení matic
• …
Otázka. Je lepší in situ algoritmus s časovou složitostí O(n2) než
algoritmus s časovou složitostí O(n log n) a prostorovou složitostí
O(n)?
Vztah mezi časem a prostorem
Teze. Někdy lze snížit časovou složitost algoritmu zvýšením jeho
prostorové složitosti (a naopak).
↑ prostor ↓ čas
• softwarová cache
• předpočítání (mezi)výsledků
↑ čas ↓ prostor
• komprese
• zvýšení abstrakce
Složitost v praxi
Tabulka časů výpočtu algoritmů o složitostech log n, n, n2, 2n a pro
vstup velikosti 10, 20, 50 a 1000. Předpokládejme, že jedna iterace
algoritmu trvá 1µs.
10 20 50 1000
log n 0,000001 s 0,000001 s 0,000002 s 0,000003 s
n 0,00001 s 0,00002 s 0,00005 s 0,001 s
n2 0,0001 s 0,0004 s 0,0025 s 1 s
2n 0,001024 s 1,048576 s 35,7 let 3, 4 · 10287 let
Poznámka. Stáří vesmíru je odhadováno na 13, 8 · 109 let.
PatternCount – analýza
def PatternCount(text, pattern):
count = 0
for i in range(0, 1 + len(text) - len(pattern)):
if text[i : i + len(pattern)] == pattern:
count += 1
return count
Pozorování
• procházíme celkem |text| − |pattern| + 1 možných umístění
• každé porovnání dvou řetězců obnáší nejvýše |pattern|
porovnání jednotlivých znaků
Závěr. Počet kroků, které vykoná funkce PatternCount, lze vyjádřit
jako O(|pattern| · (|text| − |pattern| + 1)).
FrequentWords – analýza I
def FrequentWords(text, k):
counts = dict()
frequentPatterns = set()
for i in range(0, len(text) - k + 1):
pattern = text[i : i + k]
counts[pattern] = PatternCount(text, pattern)
maxCount = max(counts.values())
for (pattern, count) in counts.items():
if count == maxCount:
frequentPatterns.add(pattern)
return frequentPatterns
Pozorování
• počet volání PatternCount je |text| − k + 1
• další příkazy nejsou určující pro dobu běhu
FrequentWords – analýza II
Složením předchozích informací dostáváme:
FrequentWords(text, k)
• složitost funkce PatternCount je O(|pattern|·(|text|−|pattern| +1))
• počet volání PatternCount je |text| − k + 1
• platí k = |pattern|
• počet kroků celkem:
k · (|text| − k + 1) · (|text| − k + 1) = k · (|text| − k + 1)2
V praxi platí k ≪ |text|, asymptotická složitost funkce FrequentWords
je tedy O(k · |text|2).
FrequentWords – praxe
Měření. Doba výpočtu funkce FrequentWords(text, k) pro k = 9 a
|text| = {1000, . . . , 9000}.
Pozorování. Naměřená data lze úspěšně proložit parabolou, což
odpovídá odhadnuté složitosti O(k · |text|2).
Hledání nejčastějších slov v textu
Dosavadní řešení. Jsme schopni navrhnout a implementovat
algoritmus se složitostí O(k · |text|2).
Zásadní otázka. Jde to i lépe?
Alternativní návrh. Počítání četností podřetězců při průchodu
textem
1. Procházej vstupní text postupně po podřetězcích délky k
1.1 Pokud se konkrétní podřetězec vyskytl poprvé, nastav jeho
četnost na 1, jinak ji zvyš o 1
2. Urči nejvyšší nalezenou četnost
3. Vrať řetězce s touto nejvyšší četností
FasterFrequentWords
Jak ukládat pro každý řetězec jeho četnost?
• počet různých řetězců délky k z písmen A, C, G, T je 4k
• každému tomuto řetězci lze přiřadit číslo od 0 do 4k − 1
Příklad pro k = 3:
AAA → 0, AAC → 1, AAG → 2, . . . , TTT → 255
Příklad převodu řetězce na číslo. A → 0, C → 1, G → 2, T → 3.
ACCTG → A · 44
+ C · 43
+ C · 42
+ T · 41
+ G · 40
ACCTG → 0 + 64 + 16 + 12 + 2
ACCTG → 94
Implementace. Vytvořím pole o velikosti 4k, kde budu ukládat
četnosti jednotlivých řetězců.
Převod řetězce na číslo – implementace
def PatternToNumber(pattern):
characters = "ACGT"
if pattern == "":
return 0
else:
return 4 * PatternToNumber(pattern[:-1]) \
+ characters.index(pattern[-1:])
def NumberToPattern(number, k):
characters = "ACGT"
if k == 0:
return ""
else:
divisor = 4 ** (k - 1)
return characters[number // divisor] \
+ NumberToPattern(number % divisor, k - 1)
FasterFrequentWords – implementace
def ComputingFrequencies(text, k):
frequencyArray = [0] * (4 ** k)
for i in range(len(text) - k + 1):
pattern = text[i: i + k]
frequencyArray[PatternToNumber(pattern)] += 1
return frequencyArray
def FasterFrequentWords(text, k):
frequentPatterns = set()
frequencyArray = ComputingFrequencies(text, k)
maxCount = max(frequencyArray)
for i in range(0, 4 ** k):
if frequencyArray[i] == maxCount:
frequentPatterns.add(NumberToPattern(i, k))
return frequentPatterns
Složitost FasterFrequentWords
Složitost jednotlivých fází algoritmu
• inicializace pole četností O(4k)
• převod řetězce na číslo (a naopak) O(k)
• průchod vstupním textem, počítání četností O(k · (|text| − k + 1))
• nalezení nejvyšší četnosti O(4k)
• výběr řetězců s nejvyšší četností O(k · 4k)
Celková složitost FasterFrequentWords. Po úpravě dostáváme
složitost O(k · |text| + k · 4k), přičemž paměťová složitost je O(4k).
Závěr. Pro k ≪ n je FasterFrequentWords výrazně rychlejší než
FrequentWords.
A jde to ještě lépe? ;-)