Programoz´as I. 1. el˝ oad´as: Algoritmusok alapjai
Sergy´an Szabolcs
[email protected] ´ Obudai Egyetem Neumann J´ anos Informatikai Kar Alkalmazott Informatikai Int´ ezet
2015. szeptember 7.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
1 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
2 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
3 / 47
1. p´elda Aut´omos´as 1
El˝omos´as. Az aut´ot mos´ oszeres l´evel bespriccelik.
2 3
Kef´es mos´as. A forg´ o kef´ek letiszt´ıtj´ak az aut´ ot. ¨ ıt´es. Az aut´ot tiszta v´ızzel le¨ Obl´ obl´ıtik.
4
Sz´ar´ıt´as. Az aut´ot leveg˝ o ´aramoltat´assal megsz´ar´ıtj´ak. Egym´ast k¨ ovet˝ o utas´ıt´asok sorozata.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
4 / 47
2. p´elda Halad´o” aut´omos´as ” 1
Ha akt´ıvhabos mos´asra fizett¨ unk el˝ o, akkor az aut´ot bespriccelik akt´ıv habbal. K¨ ul¨onben csak mos´ oszeres l´evel spriccelik be az aut´ot.
2
Ha alv´az mos´asra is el˝ ofizett¨ unk, akkor az alv´azat is v´egigspriccelik akt´ıv habbal.
3
Ha ker´ekmos´asra el˝ofizett¨ unk, akkor forg´ o kef´ek letiszt´ıtj´ak az aut´ot, a kerekekn´el pedig speci´alis ker´ektiszt´ıt´ o kef´ek moss´ak a kerekeket. K¨ ul¨onben csak a forg´ o kef´ek letiszt´ıtj´ak az aut´ ot.
4
Az aut´ ot tiszta v´ızzel le¨ obl´ıtik.
5
Ha el˝ofizett¨ unk viaszv´edelemre, akkor az aut´ ot forr´o viasz r´eteggel bevonj´ak.
6
Az aut´ ot leveg˝o´aramoltat´assal megsz´ar´ıtj´ak. Megjelennek d¨ont´esi pontok, ahol el´agazhat a v´egrehajt´as. Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
5 / 47
Euklideszi algoritmus K´et pozit´ıv eg´esz sz´am legnagyobb k¨oz¨os oszt´oja 1
Adott k´et pozit´ıv eg´esz sz´am, jel¨ olj¨ uk ezeket m-mel ´es n-nel. A kett˝o k¨oz¨ ul legyen m a nagyobbik.
2
Osszuk el m-et n-nel, az oszt´as marad´ek´at jel¨ olj¨ uk r -rel.
3
Ha r ´ert´eke 0, azaz m oszthat´ o n-nel, akkor az algoritmus v´eg´ere ´ert¨ unk. Ilyenkor a k´et sz´am legnagyobb k¨ oz¨ os oszt´oja az n ´ert´ek´evel egyezik meg, az algoritmus pedig befejez˝ odik.
4
Ha r ´ert´eke nem 0, akkor m-be t´aroljuk el az n jelenlegi ´ert´ek´et, n-be pedig az r ´ert´ek´et. Majd ugorjunk vissza a 2. pontra. Egyes l´ep´esek t¨ obbsz¨ or is v´egrehajt´asra ker¨ ulnek.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
6 / 47
Euklideszi algoritmus
K´et pozit´ıv eg´esz sz´am legnagyobb k¨oz¨os oszt´oja 1
Adott k´et pozit´ıv eg´esz sz´am, jel¨ olj¨ uk ezeket m-mel ´es n-nel. A kett˝ o k¨ oz¨ ul legyen m a nagyobbik.
2
Osszuk el m-et n-nel, az oszt´as marad´ek´at jel¨ olj¨ uk r -rel.
3
Ha r ´ert´eke 0, azaz m oszthat´ o n-nel, akkor az algoritmus v´eg´ere ´ert¨ unk. Ilyenkor a k´et sz´am legnagyobb k¨ oz¨ os oszt´ oja az n ´ert´ek´evel egyezik meg, az algoritmus pedig befejez˝ odik.
4
Ha r ´ert´eke nem 0, akkor m-be t´aroljuk el az n jelenlegi ´ert´ek´et, n-be pedig az r ´ert´ek´et. Majd ugorjunk vissza a 2. pontra.
Sergy´ an (OE NIK)
Programoz´ as I.
Konkr´et p´elda m 150 36
n 36 6
2015. szeptember 7.
r 6 0
7 / 47
Algoritmus fogalma Mi az algoritmus? Az algoritmus egy olyan g´ep”, amely valamilyen bemenetekb˝ol ” meghat´arozott l´ep´eseken kereszt¨ ul el˝ o´all´ıt valamilyen kimenetet. Bemenetek: Az algoritmus elej´en m´ar ismertek. Kimenetek: A bemenetek ´altal egy´ertelm˝ uen meghat´arozottak. Az algoritmus m˝ uk¨od´ese j´ ol meghat´arozott, azaz determinisztikus. Az algoritmus egy´ertelm˝ u, j´ ol defini´alt l´ep´esekb˝ ol ´all, melyek sz´ama minden esetben v´eges.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
8 / 47
Algoritmus alkot´as Legfontosabb l´ep´esek A folyamatot elemi l´ep´esekre bontjuk. Figyelembe vessz¨ uk az ¨ osszes felmer¨ ul˝ o lehet˝ os´eget. ¨ Ugyel¨ unk, hogy az algoritmus v´eges sok l´ep´esben v´eget ´erjen.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
9 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
10 / 47
V´altoz´ok Mi az a v´altoz´o? Az algoritmusban haszn´alt ´ert´ekeket t´arolni kell az algoritmus fut´asa sor´an. V´altoz´ ok a bemenetek, a kimenetek ´es az algoritmus megval´os´ıt´as´ahoz sz¨ uks´eges lok´alis v´altoz´ ok. Minden v´altoz´onak van neve, amellyel egy´ertelm˝ uen tudunk r´a hivatkozni. Minden v´altoz´onak van t´ıpusa is.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
11 / 47
T´ıpusok Algoritmus le´ır´asn´al haszn´alt t´ıpusok Eg´eszek (pszeudok´odban jel¨ ol´es: eg´ esz) Logikaiak (pszeudok´odban jel¨ ol´es: logikai) ´ Altal´anos t´ıpus (pszeudok´ odban jel¨ ol´es: T)
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
12 / 47
´ ekad´as Ert´ ← Az a v´altoz´onak ´ert´ek¨ ul adjuk az 5-¨ ot: a ← 5 Az ´ert´ekad´as bal oldal´an egyetlen v´altoz´ o ´allhat. A jobb oldalon egy ´ert´ek, egy v´altoz´ o vagy egy kifejez´es ´allhat. Mindig a baloldali v´altoz´ o kapja meg a jobboldali ´ert´eket, visszafel´e nem t¨ort´enik ´ert´ekad´as.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
13 / 47
Csere ↔ Az a ´es b v´altoz´o megcser´el´es´enek l´ep´esei: seg´ed ← a a←b b ← seg´ed R¨ovidebb jel¨ol´es: a ↔ b
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
14 / 47
Kifejez´esek Mi az a kifejez´es? Sz´amkifejez´esben sz´amokat tartalmaz´ o v´altoz´ ok, konkr´et sz´am´ert´ekek ´es ezeket ¨osszekapcsol´ o matematikai m˝ uveletek szerepelhetnek. P´elda:
bal − jobb + 3, 2 ahol bal ´es jobb egy-egy v´altoz´ o. A sz´amkifejez´esek ki´ert´ekel´ese a matematik´aban megismert szab´alyok szerint t¨ort´enik.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
15 / 47
Logikai t´ıpus ´ ekek ´es m˝uveletek Ert´ K´et lehets´eges ´ert´ek: igaz hamis
M˝ uveletek: Neg´al´as: ¬ ´ kapcsolat: ∧ Es Vagy kapcsolat: ∨
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
16 / 47
Logikai t´ıpus Neg´al´as l logikai ´ert´eke hamis igaz
¬l logikai ´ert´eke igaz hamis
´ valamint vagy kapcsolat Es l1 log. ´ert´eke hamis hamis igaz igaz
Sergy´ an (OE NIK)
l2 log. ´ert´eke hamis igaz hamis igaz
l1 ∧ l2 log. ´ert´eke hamis hamis hamis igaz
Programoz´ as I.
l1 ∨ l2 log. ´ert´eke hamis igaz igaz igaz
2015. szeptember 7.
17 / 47
Logikai t´ıpus R¨ovidz´ar ki´ert´ekel´es Ha egy ´es kapcsolat els˝ o tagja hamis, akkor a m´asodik tag m´ar nem is ker¨ ul ki´ert´ekel´esre, mert a teljes ´es kapcsolat hamis lesz. Ha egy vagy kapcsolat els˝ o tagja igaz, akkor a m´asodik tag m´ar nem is ker¨ ul ki´ert´ekel´esre, mert a teljes vagy kapcsolat igaz lesz.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
18 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
19 / 47
T¨omb¨ok Mi a t¨omb? T¨obb azonos t´ıpus´ u ´ert´eket lehet egy v´altoz´ oban elt´arolni. A t¨omb elemeire indexel´essel hivatkozunk. A harmadik elem el´er´ese: x[3]. Az indexel´es 1-t˝ol indul. x:
2
3
5
7
11
13
17
19
1
2
3
4
5
6
7
8
T¨omb l´etrehoz´asa ´trehoz(eg´ x ← Le esz)[8]
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
20 / 47
K´etdimenzi´os t¨omb¨ok P´elda
1 2 3 4
1
2
3
4
5
6
3 2 6 4
5 9 8 1
8 3 2 0
4 0 1 2
7 6 1 7
1 4 5 8
Elemre hivatkoz´as: x[2, 5]
K´etdimenzi´os t¨omb l´etrehoz´asa ´trehoz(eg´ x ← Le esz)[4, 6] Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
21 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
22 / 47
Szekvencia Utas´ıt´asok egym´as ut´ani v´egrehajt´asa ´trehoz(eg´ x ← Le esz)[3] x[1] ← 5 x[2] ← 8 x[3] ← 11
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
23 / 47
El´agaz´as Utas´ıt´as felt´eteles v´egrehajt´asa ha a < 0 akkor a ← −a el´ agaz´ as v´ ege √ b← a
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
24 / 47
El´agaz´as K´etir´any´u el´agaz´as ha a < 0√akkor b ← −a k¨ ul¨ onben √ b← a el´ agaz´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
25 / 47
El´agaz´as T¨obbir´any´u el´agaz´as ha a > 0 akkor √ b← a k¨ ul¨ onben √ha a < 0 akkor b ← −a k¨ ul¨ onben b←0 el´ agaz´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
26 / 47
Ciklus El¨oltesztel˝os ciklus ciklus am´ıg felt´etel utas´ıt´asok ciklus v´ ege
P´elda ciklus am´ıg r 6= 0 m←n n←r r ← m mod n ciklus v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
27 / 47
Ciklus H´atultesztel˝os ciklus ciklus utas´ıt´asok am´ıg felt´etel
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
28 / 47
Ciklus Sz´aml´al´os ciklus ciklus ciklusv´altoz´o ← kezdeti´ert´ek-t˝ ol v´eg´ert´ek-ig utas´ıt´asok ciklus v´ ege
P´elda ´trehoz(eg´ x ← Le esz)[5] ciklus i ← 1-t˝ol 5-ig x[i] ← i 2 ciklus v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
29 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
30 / 47
Struktur´alt programoz´as Struktur´alt programnak tekintj¨ uk azokat a programokat, amelyek csak a megengedett elemi programokat tartalmazz´ak a megengedett programkonstrukci´ok (vez´erl´esi szerkezetek) alkalmaz´as´aval. Elemi programok u ¨res program ´ert´ekad´as (´allapot v´altoztat´as) jele: ←
Megengedett konstrukci´ ok szekvencia el´agaz´as ciklus
Bizony´ıthat´o, hogy a fenti szab´alyok megtart´as´aval minden algoritmussal megoldhat´ o feladatra adhat´ o is megold´as.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
31 / 47
Modul´aris programoz´as Az elk´esz´ıtend˝o programot egyetlen utas´ıt´assal szeretn´enk megoldani. Ha ez nem siker¨ ul, akkor t¨ obb utas´ıt´assal pr´ ob´alkozunk, melyek egyes r´eszfeladatokat val´os´ıtanak meg. Addig folytatjuk ezt a r´eszfeladatokra bont´ast, m´ıg minden r´eszfeladatot siker¨ ul megval´ os´ıtani elemi utas´ıt´asok felhaszn´al´as´aval. ¨ Osszefoglalva: A teljes feladatot r´eszekre bontjuk, majd ezeket a visszavezet´es m´odszer´evel megoldjuk.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
32 / 47
F¨uggv´enyek vs. elj´ar´asok F¨uggv´eny Egy konkr´et algoritmust val´ os´ıt meg. M´as f¨ uggv´enyek vagy elj´ar´asok megh´ıvhatj´ak. Vannak bemenetei. Van visszat´er´esi ´ert´eke (kimenete). Ezt a vissza kulcssz´oval adjuk meg.
Elj´ar´as Egy konkr´et algoritmust val´ os´ıt meg. M´as f¨ uggv´enyek vagy elj´ar´asok megh´ıvhatj´ak. Vannak bemenetei. Kimenete csak param´etereken kereszt¨ ul lehet. Ehhez c´ımszerint adjuk ´at a param´etert. Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
33 / 47
Euklideszi algoritmus F¨uggv´ennyel megval´os´ıtva Bemenet: m − eg´ esz, n − eg´ esz Kimenet: n − eg´ esz 1: f¨ uggv´ eny LNKO(m, n) 2: r ← m mod n 3: ciklus am´ıg r 6= 0 4: m←n 5: n←r 6: r ← m mod n 7: ciklus v´ ege 8: vissza n 9: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
34 / 47
Euklideszi algoritmus Elj´ar´assal megval´os´ıtva Bemenet: m − eg´ esz, n − eg´ esz Kimenet: n − eg´ esz 1: elj´ ar´ as LNKO(m, c´ımszerint n) 2: r ← m mod n 3: ciklus am´ıg r 6= 0 4: m←n 5: n←r 6: r ← m mod n 7: ciklus v´ ege 8: elj´ ar´ as v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
35 / 47
F¨uggv´eny h´ıv´asa Relat´ıv pr´ım vizsg´alat Bemenet: x − eg´ esz t¨ omb, n − eg´ esz (t¨ omb m´erete), value − eg´ esz Kimenet: y − logikai t¨ omb ´ lat(x, n, value) 1: f¨ uggv´ eny Relat´ıvPr´ımVizsga ´ 2: y ← Letrehoz(logikai)[n] 3: ciklus i ← 1-t˝ol n-ig 4: ha LNKO(x[i], value) = 1 akkor 5: y [i] ← igaz 6: k¨ ul¨ onben 7: y [i] ← hamis 8: el´ agaz´ as v´ ege 9: ciklus v´ ege 10: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
36 / 47
Tartalom 1
Algoritmus fogalma
2
V´altoz´ok, t´ıpusok ´es kifejez´esek
3
T¨ omb¨ok
4
Vez´erl´esi szerkezetek
5
Algoritmusok le´ır´asa pszeudok´ oddal
6
Hat´ekonys´ag, fut´asi id˝ o elemz´ese
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
37 / 47
Algoritmusokkal kapcsolatos elv´ar´asok Mikor j´o” egy algoritmus? ”
Megb´ızhat´o: Helyesen m˝ uk¨ odik. Kisz´am´ıthat´o: Adott bemenet eset´en mindig ugyanazt a kimenetet szolg´altatja. Egyszer˝ u: K¨onnyen meg´erthet˝ o. Hat´ekony: Kev´es mem´ oria ig´enye van. Kev´es” a fut´asi ideje. ”
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
38 / 47
El˝oad´asra j´ar´o hallgat´ok sz´am´anak meghat´aroz´asa H´anyan vannak itt a teremben? Hogyan tudn´ank ezt hat´ekonyan megsz´amolni?
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
39 / 47
Sz´o keres´ese sz´ot´arban Hogyan tudunk hat´ekonyan sz´ ot keresni egy sz´ ot´arban?
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
40 / 47
Algoritmus l´ep´essz´ama Egy algoritmus l´ep´essz´ama alatt azt ´ertj¨ uk, hogy h´any elemi m˝ uveletet (´ert´ekad´as, ¨ osszehasonl´ıt´as, stb.) kell v´egrehajtani adott bemenet mellett. Egy algoritmus fut´asi ideje f¨ ugg az algoritmust megval´os´ıt´o programt´ol, a programoz´asi nyelvt˝ ol, a sz´am´ıt´ og´ept˝ol, stb. Algoritmuselm´eletben a fut´asi id˝ ot a l´ep´essz´ammal jellemezz¨ uk.
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
41 / 47
Fut´asi id˝o H´any l´ep´esben fut le az algoritmus? Bemenet: x − eg´ esz t¨ omb, n − eg´ esz Kimenet: db − eg´ esz ´ tAdo ´ Elempa ´ rokSza ´ ma(x, n) 1: f¨ uggv´ eny Nulla 2: db ← 0 3: ciklus i ← 1-t˝ol (n − 1)-ig 4: ciklus j ← (i + 1)-t˝ ol n-ig 5: ha x[i] + x[j] = 0 akkor 6: db ← db + 1 7: el´ agaz´ as v´ ege 8: ciklus v´ ege 9: ciklus v´ ege 10: vissza db 11: f¨ uggv´ eny v´ ege
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
42 / 47
Fut´asi id˝o Felt´etel ki´ert´ekel´esek sz´ama (n − 1) + (n − 2) + . . . + 2 + 1 =
(n − 1) + 1 n (n − 1) · (n − 1) = 2 2
´ ekad´asok sz´ama Ert´ Legjobb esetben: 0-szor Legrosszabb esetben:
n(n−1) -szer 2
Algoritmus fut´asi ideje O n2
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
43 / 47
Fut´asi id˝o anal´ızis´enek fajt´ai Legrosszab eset anal´ızis T (n): a maxim´alis fut´asi id˝ o, amely b´armely n elem˝ u sorozat eset´en a rendez´eshez legfeljebb sz¨ uks´eges
´ Atlagos eset anal´ızis T (n): a v´arhat´ o fut´asi id˝ o, amely az n elem˝ u sorozatok rendez´es´ehez sz¨ uks´eges
Legjobb eset anal´ızis Magunkat verj¨ uk ´at, ha ezzel foglalkozunk
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
44 / 47
Fut´asi id˝o Fut´asi id˝ok o¨sszehasonl´ıt´asa
T (n)
800 600 400
9 100
· n2 n · log2 n
200 0 0
20
40
60
80
100
n
Nagy ord´o jel¨ol´es Azt mondjuk, hogy a T (n) fut´asi id˝ o O (f (n))-es, ha l´etezik olyan c konstans, hogy el´eg nagy n ´ert´ekek eset´en T (n) ≤ c · f (n). Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
45 / 47
Fut´asi id˝o Gyakran el˝ofordul´o nagys´agrendek Fut´asi id˝o nagys´agrendje O(1) O(log n) O(n) O(n log n) O(n2 ) O(n3 ) O(2n )
Sergy´ an (OE NIK)
Fut´asi id˝ o nagys´agrendj´enek elnevez´ese Konstans Logaritmikus Line´aris Logaritmetikus N´egyzetes K¨ ob¨ os Exponenci´alis
Programoz´ as I.
2015. szeptember 7.
46 / 47
Fut´asi id˝o
T (n)
Gyakori nagys´agrendek 6 5 4 3 2 1 0
O(log n)
20
40
60
80
100
n
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
47 / 47
Fut´asi id˝o Gyakori nagys´agrendek 100
T (n)
80 60
O(log n) O(n)
40 20 0 20
40
60
80
100
n
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
47 / 47
Fut´asi id˝o
T (n)
Gyakori nagys´agrendek 600 500 400 300 200 100 0
O(log n) O(n) O(n log n) 20
40
60
80
100
n
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
47 / 47
Fut´asi id˝o Gyakori nagys´agrendek 10,000
T (n)
8,000 6,000
O(log n) O(n) O(n log n) O(n2 )
4,000 2,000 0 20
40
60
80
100
n
Sergy´ an (OE NIK)
Programoz´ as I.
2015. szeptember 7.
47 / 47
