O(n) je, kdyz provedes n kroku.
Chces pridat na konec seznamu 15 zaznamu, tak provedes 15x pridani.
Chces zkopirovat 1 zaznam, 1x pridani.
Chces seradit pole o 15 prvcich, pak
- seradis skupiny 1 a 1.. 1 krok na skupinu, celkem pro vsechny ~15/2 (zaokrouhleno nahoru) = 8
- seradis skupiny 2 a 2 ... 3 kroky (soucet-1) na skupinu, celkem pro vsechny ~(15/4)*3 = 12
- seradis skupiny 4 a 4 ... 7 kroku na skupinu ~15/8*7 = 2*7 = 14
- seradis skupiny 8 a 8 ... priblizne 15 kroku, 1*15 = 15
celkem tedy max 49 kroku, min = 1+2+4+8 = 15
// pro 2 a 2 nepotrebujes porovnavat uz kazde s kazdym, to uz jsi udella pri porovnavani 1 a 1, dvou po sobe jdoucich prvku a seradil je
n/2*(n+1) = 15/2*16 = 120 soucet rady 1+2+3... // to je kdybys porovnaval kazde s kazdym uz od zacatku
Slozitosti u serazovacich algoritmu
O(n) = 15
O(n log n) = 15 * log 15 = 15 * 1.176 = 18
O(n^2) = 15*15 = 225
http://popular.fbmi.cvut.cz/…ozitost.aspx
https://cs.wikipedia.org/…D_algoritmus
O(n^2) - je, ze vemes prvni prvek a porovnas se vsemi, druhy a opet se vsemi, takze delas cylus(15) {cyklus(15){...}}, proste 15x opakujes 15 operaci.
Kdyz bys musel pridat ten prvek na treti pozici a puvodni pole ma 15 prvku, tak ted zalezi na tom, jak funguje programovaci jazyk.
- Bud ma rezervovanou pamet a je schopen posunout prvni 2 prvky vys. Pak provede 2 presuny a 1 pridani, 3 operace ... 3
- Nebo musi posunout cele pole pod treti pozici, pak provede 15-2 operaci presunu a 1 pridani ... 14
- Nebo ma specialni pamet pro ulozeni poradi prvku (treba databaze) a prida prvek na konec do poradi a na konec do pole. pridani do tohoto pole je obvykle casove skoro mizive, takze pak je to jen casove operace 1 pridani.prvku ... 1