Tartalomjegyzék
Algoritmusok bonyolultsága
- Szerző: Sallai András
- Copyright © 2014, Sallai András
- Szerkesztve: 2014, 2017, 2022
- Licenc: CC BY-SA 4.0
- 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.
Jelzések
Jelölések:
- θ - átlagos eset
- O - legrosszabb eset
- Ω - legjobb eset
Átlagos futások
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 gnuplot néhány vonatkozása
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/