< Algoritmusok

Algoritmusok bonyolultsága

Szerző: Sallai András

Copyright © Sallai András, 2014, 2017, 2022

Licenc: CC Attribution-Share Alike 4.0 International

Web: https://szit.hu

Hatékonyságvizsgálat

Azt vizsgáljuk, hogy a bemenet növekedésével hogyan nő a számítási igény.

A következő ábrán néhány lehetséges lefutást látunk.

A függőleges tengely egy algoritmus lehetséges a számításigényét jelképezi. A futási idő, vagy a processzoridő nincs az ábrán.

Az ábra jobb felső sarkában azt látjuk, hogyan állítottam elő a gnuplot programmal a függvényeket. A Θ jelölés [théta].

konstans idő Θ(1) - egyetlen művelet

logaritmikus idő Θ(log2 n)

lineáris idő Θ(n)

n * logaritmikus idő Θ( n log2 n)

kvadratikus idő Θ(n2)

faktoriális idő Θ(n!)

A log2 n kifejezést néha így rövidítik: log n.

A gnuplot parancs:

plot [1:40] [-10:40] gamma(x+1), x**2, x*log(x)/log(2),x,log(x)/log(2),1

A gamma() függvény a faktoriális általánosítása.

A gnuplot logaritmusfüggvényei:

log(x) x e alapú logaritmusa (ln x)

log10(x) x 10-es alapú logaritmusa (lg x)

Faktoriális

n	n2	n!
1	1	1
2	4	2
3	9	6
4	16	24
5	25	120
6	36	720
7	49	5040
8	64	40 320
9	81	362 880
10	100	3 628 800

Néhány algoritmus

A legrosszabb esetet nagy O-val jelöljük.

Néhány algoritmus legrosszabb esete:

beszúró rendezés O(n2)

buborék rendezés O(n2)

gyors rendezés O(n2)

shell-rendezés O(n log2 n) - függ a használt sorozattól

összefésülő rendezés O(n log n)

A legrosszabb esetek néhány függvénye

A fenti függvényeken kívül szokás még a harmadik hatvány, az exponenciális függvény használata az algoritmusok jellemzésére. Hasonlítsuk össze ezeket a második hatvánnyal és a faktoriálissal.

A függőleges tengelyt megnöveltem 1000-re, vagyis nagy elem szám esetén a legrosszabb eset a faktoriális marad. Az eltérés azonban elég kicsi a faktoriális és az exponenciális között.

Adatstruktúrák

Adatstruktúra	Időigény
Átlag	Legrosszabb
Elérés	Keresés	Beszúrás	Törlés	Elérés	Keresés	Beszúrás	Törlés
Tömb	Θ(1)	Θ(n)	Θ(n)	Θ(n)	O(1)	O(n)	O(n)	O(n)
Verem	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)
Sor	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)
Egyszeresen linkelt lista	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)
Kétszeresen linkelt lista	Θ(n)	Θ(n)	Θ(1)	Θ(1)	O(n)	O(n)	O(1)	O(1)
Bináris keresés	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(n)	O(n)	O(n)	O(n)
B-Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
Hash tábla	n/a	Θ(1)	Θ(1)	Θ(1)	n/a	O(n)	O(n)	O(n)

Forrás: https://www.bigocheatsheet.com/

Rendezések

Rendező algoritmusok
Algoritmus	Időigény
Legjobb	Átlagos	Legrosszabb
Gyors-rendezés	Ω(n log(n))	Θ(n log(n))	O(n^2)
Buborék-rendezés	Ω(n))	Θ(n^2)	O(n^2)
Beszúrásos rendezés	Ω(n)	Θ(n^2)	O(n^2)
Shell rendezés	Ω(n log(n))	Θ(n(log(n))^2)	O(n(log(n))^2)

Forrás: https://www.bigocheatsheet.com/