O notation – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

O notation – Python – Fórum – Programujte.comO notation – Python – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
sliziky
~ Anonymní uživatel
11 příspěvků
28. 12. 2014   #1
-
0
-

Zdravím ,mám program dajme tomu s 2x for ( nie vnorene podmienky) a chcel by som.zistiť O notaciu..viem že pri vnorenych to už je O(n2) ..ale ak su len 2 for zvlášť tak to som nenašiel:) a popr ak mám nejaký sort napr bubble ktorý ma O(n2) a napr for,čiže O(n) tak stačí nájsť maximalnu notaciu t.j. O(n2) z bubblesortu? Ďakujem za odpoveď :)

Zasláno z mobilního telefonu.

Nahlásit jako SPAM
IP: 78.98.60.–
Reklama
Reklama
lukas.balaz0
Super člen
28. 12. 2014   #2
-
+1
-
Zajímavé
Kit +
Nahlásit jako SPAM
IP: 80.242.41.–
lukas.balaz0
Super člen
28. 12. 2014   #3
-
0
-

#1 sliziky
A prosim ta, O(n2) je rozdiel ako O(n^2) ... dost ma to zmiatlo

Nahlásit jako SPAM
IP: 80.242.41.–
sliziky
~ Anonymní uživatel
11 příspěvků
28. 12. 2014   #4
-
0
-

Chcel som to najskor n^2 ale reku že si domyslite...dik :)

Zasláno z mobilního telefonu.

Nahlásit jako SPAM
IP: 78.98.60.–
hanpari0
Návštěvník
29. 12. 2014   #5
-
0
-

#1 sliziky
Dvě smyčky za sebou jsou O(n), přesněji řečeno

jedna smyčka O(n)

dvě stejné smyčky za sebou O(2n) => O(n)

Jednoduše, je to stále lineární.

Nahlásit jako SPAM
IP: 178.72.234.–
sliziky
~ Anonymní uživatel
11 příspěvků
29. 12. 2014   #6
-
0
-

Aha ďakujem :)

Zasláno z mobilního telefonu.

Nahlásit jako SPAM
IP: 78.98.60.–
hanpari0
Návštěvník
29. 12. 2014   #7
-
+1
-
Zajímavé

#6 sliziky
Není zač, pokud se chceš podívat, jaký je rozdíl ve škálování, můžeš si zkusit tenhle jednoduchy program pro python 3.x. Na nem krásně uvidíš rozdíl mezi x*n a n**2.

from turtle import Turtle
def jedna_smycka(n):
    return sum(1 for i in range(n))

def x_smycek(n,x):
    return x * jedna_smycka(n)

def vnorena_smycka(n):
    return n * jedna_smycka(n)


x = 10 # pocet smycek za sebou
prvky = 100  # pocet prvků, jak program škáluje s počtem prvků 
t = Turtle()
vyska = vnorena_smycka(prvky) + 10
t.screen.setworldcoordinates(0,0, prvky+20,
                             vyska)
t.up()
t.goto(0,vyska*0.9)
t.down()
t.write("Počet prvků: {}:".format(prvky))
t.hideturtle()

jedna = Turtle()
jedna.pencolor("red")
x_smycka = Turtle()
x_smycka.pencolor("blue")
kvadraticka = Turtle()
kvadraticka.pencolor("green")

for i in range(prvky):
    jedna.goto(i, jedna_smycka(i))
    x_smycka.goto(i, x_smycek(i,x))
    kvadraticka.goto(i, vnorena_smycka(i))

jedna.write("O(n) Jedna smyčka.")
x_smycka.write("O(n) Počet smyček: {}.".format(x))
kvadraticka.write("O(n**2) Kvadratická.")

Připojen obrázek.

Nahlásit jako SPAM
IP: 178.72.234.–
sliziky
~ Anonymní uživatel
11 příspěvků
29. 12. 2014   #8
-
0
-

Ja len nechapem ze ako v niektorych pripadoch urcite tu notaciu :))

Nahlásit jako SPAM
IP: 78.98.60.–
hanpari0
Návštěvník
30. 12. 2014   #9
-
+1
-
Zajímavé
Kit +

#8 sliziky
To také není nic jednoduchého, pokud nejde vyslovené o jednoznačné případy.

U většiny algoritmů budeš rád, když stanovíš nejhorší možný případ, přičemž někdy se ti to nemusí podařit: (viz Časová složitost a třídy P a NP na wikipedii)

Proto jsem ti úmyslně odpovídal pouze na tvůj dotaz, jaký je rozdíl mezi vnořenou smyčkou a smyčkami za sebou.

Když se podíváš na wikipedii:

http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost

Najdeš tam toto:

Například časová složitost [O(N)] (tzv. lineární) říká, že doba trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu. Na druhou stranu u složitosti [O(N^2)] se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší čtyřikrát. U časové složitosti [O(1)] naopak na délce vstupu vůbec nezáleží a potřebný čas je stále stejný. Podobně je tomu i u prostorové složitosti, jen s tou změnou, že se jedná o potřebné paměťové (prostorové) nároky v závislosti na délce vstupních dat.

Což jsem ti ukázal pomocí jednoduchého prográmku.

Co ti tedy není jasné?

Nahlásit jako SPAM
IP: 178.72.234.–
sliziky
~ Anonymní uživatel
11 příspěvků
30. 12. 2014   #10
-
0
-

Dajme tomu ze mam program s 2x for cize O(2n) = O(n) ..ak sa nemylim :) ..a potom mam este Timsort s O(n log n)...teraz musim urcite casovu zlozitost...to bude teda O(n log n)? :)

Nahlásit jako SPAM
IP: 78.98.6.–
hanpari0
Návštěvník
30. 12. 2014   #11
-
0
-

#10 sliziky
Ano, přesně tak. Můžeš použít ten prográmek, aby ses podíval. Ovšem, aby se ti to projevilo, musel bys použít podstatě vyšší stupen prvků, abys videl

V podstate bys mel dostat neco jako O(n*log(n) + 2*n) => O(n*log(n)), bere se v potaz jen ten nejvyšší stupen bez případných koeficientů.

Nahlásit jako SPAM
IP: 178.72.234.–
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, 68 hostů

Podobná vlákna

Oop, zacyklena trida — založil .

Proměné v objektu — založil Kall_Ell

Nahlad obrázkov — založil Tomáš Lacko

 

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