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

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.

http://www.mff.cuni.cz/fakulta/mfp/download/books/ksp_-_programatorske_kucharky.pdf - prva kapitola, tam to je vyborne vysvetlene

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

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

Zasláno z mobilního telefonu.

#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í.

Aha ďakujem :)

Zasláno z mobilního telefonu.

#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.

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

#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é?

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

#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ů.