MFF UK / Ústav teoretické fyziky / Tomáš Ledvinka
Přednášky
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
  Úvod
  Programy a algoritmy
  Píšeme program
  Píšeme program II
  Procedury a funkce
  Malujeme funkce
  Chyby. Typy I.
  Typy II. Pole a Záznamy
  Pole II.Řetězce.Soubory.
  Gnuplot.Interpolace...
  Matice. Velké O...
    Matice
    Soustava lineárních rovnic
    Časová náročnost algoritmu
    Seznamy
  Fronta,Zásobník. Postscript
  Bin. soubory, ...
  Ukazatele,Objekty, ...
Počítačová algebra
Klasická elektrodynamika (2.r)
Vybrané partie OTR

Cvičení
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
Teoretická mechanika (2.r)
Klasická elektrodynamika (2.r)


Věda
. . . . . . . . . . . . . . . . . . . . . . . . . .
Diskové zdroje v OTR
Hyperbolické systémy v OTR


Kontakt
. . . . . . . . . . . . . . . . . . . . . . . . . .
Email
Konzultační hodiny


Ostatní
. . . . . . . . . . . . . . . . . . . . . . . . .
Mallorca
Ze společnosti

Časová a paměťová náročnost algoritmu

Vezměme jednoduchý obrázek

tušíme, že věci se zesložití, pokud vezmeme větší počet vrcholů

co můžeme říci o chování pro velký počet vrcholů (47)?

a takto vypadá detail

Nechť počet vrcholů je N. Pak se můžeme například ptát

  • kolik je potřeba čar k nakreslení takového obrázku ?
  • kolik různých průsečíků je v takovém grafu ?

Podobně se můžeme ptát třeba

  • jak dlouho poběží program, který bude v takovém grafu hledat nejkratší vytnutou úsečku?

Stejně tak nás může zajímat kolik paměti bude program potřebovat.

Pro každý problém zkusíme najít charakteristické N číslo udávající jeho velikost. Ne vždy je to možné ale pro představu pár příkladů:

Počet položek na skladu v programu pro skladové hospodářství.
Počet neznámých v soustavě lineárních rovnic.
Počet jednání které má vyřídit obchodní cestující.
Počet souborů, které chceme efektivně vypálit na cédéčka.

Nyní se můžeme ptát jak se bude program zabývající se výše uvedenými problémy chovat při růstu onoho charakteristického čísla N. Samozřejmě, pokud neplánujeme růst skladu, zvyšování počtu neznámých atp., nemusíme se tím zabývat. I ve fyzice se ale projevuje tendence počítat složitější a složitější problémy (třeba ty jednodušší už někdo vyřešil) a tak na problém velkého N můžeme narazit.

Při porovnávání různých algoritmů máme možnost porovnat, jak se chovají pro různé velikosti vstupních dat přímo

Někdy závisí doba řešení problému na konkrétních vstupních hodnotách, často ale, jak jsme viděli, u soustav lineárních rovnic, závisí pouze na velikosti problému.

Vzpomeneme-li si na definici algoritmu, víme že jde o posloupnost elementárních operací. Předpokládejme nejdříve, že elementárními operacemi rozumíme základní operce jako jsou sčítání, násobení, větvení, přístup k jednoduché proměnné, přístup k prvku pole volání či návrat z podprogramu atp. Změříme-li dobu, kterou potřebuje počítač k provedení každé z těchto operací a budeme-li předpokládat, že celý program se vykoná za dobu odpovídající součtu těchto jednotlivých operací, víme jak spočíst dobu potřebnou k provedení programu. Řekněme třeba, 6e podprogram pro skalární součin dvou vektorů

Function SkalSoucin(const A,B:tVektor):real;
var i:integer;
begin
  s:=0;
  for i:=0 to High(A) do s:=s+A[i]*B[i];
  SkalSoucin := 0;
end;

provede následující operace (časy jsou z dobrých důvodů jen přibližné a konkrétní hodnoty nedůležité, mysleme si ale, že časy jsou v nanosekundách nebo, ještě lépe, v tiknutích hodin procesoru počítače).

Operace Čas Počet Celkem
Předávání parametrů 4 1 4
Vynulování proměnné 2 1 2
Zjištení horní meze pole A 30 1 30
Příprava cyklu 6 1 6
Načetní A[i] 3 N 3N
Přinásobení B[i] 6 N 6N
Přičtení s 6 N 6N
Uložení do s 4 N 4N
Zvětšení i 2 N 2N
Skok na začátek cyklu 6 N-1 6N-6
Přiřazení do výsledku 4 1 4
Návrat z funkce 10 1 10

a tedy celkový čas T = 27 N + 50.

Podobně bychom pro násobení matice vektorem dostali třeba

T = 36 N^2 + 44 N +26

Pokud nás ale zajímá chování pro větší N, je rozhodující první člen. Píšeme

T ~ 36 N^2

Určit koeficient přesně je ale velmi obtížné a asi jedinou možností je až analýza měření závislosti času výpočtu na N. Pokud chceme mluvit o výkonu algoritmu v okamžiku jeho návrhu ještě před jeho kódováním a nákupem počítače, ukazuje se, že nejjednoduuší je prostě psát

T = O(N^2)

Velké O(f) je označení pro libovolnou takovou funkci g, která splňuje vztah

0 < lim | g / f | < nekonečno pro N jdoucí do nekonečna

Následující tabulka má ilustrovat, že opravdu rozhodující je právě řád, nikoli konkrétní hodnota koeficientu u vedoucího členu.

N N.log2 N N^2 N^3 2^N N!
3 6 9 27 8 6
10 30 100 1 000 1 024 3 628 800
30 150 900 27 000 1.1 E9 2.65 E32
100 700 10 000 1 000 000 1.27 E30 9.33 E157
1 000 10 000 1 000 000 1 E9 1.1 E 300 4.02 E2567
10 000 140 000 100 000 000 1 E15 2.0 E3010 2.84 E35659

Mimochodem, od velkého třesku uplynulo asi 3x10^26 nanosekund.

Vztah O(f) . O(g) = O(f . g) nám pak umožňuje místo rozkladu algoritmu na elementární kroky O(1), uvažovat strukturovaně.

Třeba Gauss-Jordanova eliminace (za předpokladu, že počet pravých stran je <=O(N) ) pro každý řádek ( tedy O(N) krát) provádí
# hledání největšího prvku na/pod diagonálou O(N)
# normalizace O(N)
# odečtení násobku řádku od všech ostatních O(N^2)

A na začátku a na konci ještě nějaké kopírování O(N^2)

Odsud máme
O(N^2) + O(N)*( O(N)+ O(N)+ O(N^2)) = O(N^3)

V tabulce si pak snadno najdeme, pro jaká N jde o zelený, oranžový či hnědý problém.

Podobně jako se s rostoucím N nějak chová čas potřebný k provedení výpočtu, nějak rostou i paměťové nároky. Protože nad velikostí datových struktur máme trochu lepší kontrolu, lze v praxi velmi dobře odhadnout co se vejde a co ne. V rozvahách o schůdnosti různých algoritmů ale také často vystačíme s notací velkého O.

.