Felhasználói eszközök

Eszközök a webhelyen


oktatas:programozas:algoritmusok:bonyolultsag

< Algoritmusok

Algoritmusok bonyolultsága

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)

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)
oktatas/programozas/algoritmusok/bonyolultsag.txt · Utolsó módosítás: 2022/10/06 23:27 szerkesztette: admin