Algoritmusok bonyolultságnak mérése esetén, ha két algoritmus bonyolultságát össze adom, akkor pl: O (n^3) +O (n^2) =O (n^3)? és O (n^3) +O (n^3) =O (n^3)?
válasza:
válasza:Ha konstans sokat adsz össze, akkor a szereplő futásidők közül a maximum lesz az eredmény.
Ha n-től függő darabot adsz össze, akkor ott már vigyázni kell.
válasza: válasza:Leszámítva, hogy ez nem a bonyolultságot, hanem a pontosságot (hibát) fejezi ki.
Az ordó azt mutatja meg, az adott algoritmus hibája az "n" hányadik hatványával arányos. És ha valami a sokkal nagyobb harmadik hatvánnyal arányos, akkor ahhoz egy második hatványú hibát adva, az eredmény még mindig a harmadik hatvánnyal arányos. Röviden szólva, a nagyságrendben mindig a legmagasabb hatvány számít csak.
Én ezt nem így tudom.
Ezt a definíciót hazsnáltam:
nformatikában általában egy algoritmus futásidejének jellemzésére használjuk: a vizsgált függvény a futáshoz szükséges időt adja meg a bemenet hosszának függvényében. Leegyszerűsítve, egy O(n^2) futásidejű algoritmus kétszer akkora méretű bemenetre négyszer annyi ideig fog futni, háromszor akkora bemenetre kilencszer annyi ideig. Míg maga a futásidőt leíró függvény függ az implementáció részleteitől és a futtatáshoz használt architektúrától, az algoritmus nagy ordója csak az algoritmus alapelvétől függ.
válasza:Az O() nagyságrendet jelöl. A hibát is O()-ban, azaz nagyságrendben mér(het)jük, pont ugyanúgy, ahogy a futásidőt.
Hibára is érvényes, amit írtam. Konstans darab O() összege esetén az eredmény a legnagyobb tag lesz. (Speciálisan polinomok esetén a legnagyobb kitevőjű.)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!