Časová zložitosť funkcií zoznamu – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Itej
~ Anonymní uživatel
13 příspěvků
6. 1. 2016   #1
-
0
-

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 :-)

Nahlásit jako SPAM
IP: 78.98.30.–
Reklama
Reklama
sleepy
~ Anonymní uživatel
422 příspěvků
7. 1. 2016   #2
-
0
-

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

Nahlásit jako SPAM
IP: 90.64.83.–
sleepy
~ Anonymní uživatel
422 příspěvků
7. 1. 2016   #3
-
0
-
Nahlásit jako SPAM
IP: 90.64.83.–
Itej
~ Anonymní uživatel
13 příspěvků
7. 1. 2016   #4
-
0
-

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

Nahlásit jako SPAM
IP: 78.98.30.–
sleepy
~ Anonymní uživatel
422 příspěvků
8. 1. 2016   #5
-
0
-

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

Nahlásit jako SPAM
IP: 90.64.83.–
peter
~ Anonymní uživatel
2528 příspěvků
8. 1. 2016   #6
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:2601:26c:7d:25cb...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 20 hostů

Podobná vlákna

Casova zlozitost — založil vird

Výpis zoznamu — založil allicce

Funkcia výpisu zoznamu — založil Filip

Transformacia zoznamu v txt — založil kibukaj

Zobrazovanie zoznamu v IE 6 a IE7 — založil radypala

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý