Časová zložitosť funkcií zoznamu – Python – Fórum – Programujte.com

Zdravím,chcem sa spýtať, majme 2 zoznamy , jeden prázdny ,druhý o veľkosti n. Ak použijem napríklad funkciu append , t.j.  

prazdnyZoznam.append(druhyZoznam)

,bude časová zložitosť tejto funkcie O(n)? Vďaka moc :-)

O(1) lebo pridavas jeden element a to cely list.

http://www.laurentluce.com/posts/python-list-implementation/

Toto ti to mozno ozrejmi. Ide o to ze si pridal do prazdneho listu referenciu na iny list.

A ak máme extend (+) ,tj prazdnyZoznam+=druhyZoznam ? Ďakujem :-)

No minimalne musis prekopirovat vsetky elementy z jednoho zoznamu do druheho, cize O(n).

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