[[oktatas:programozás:algoritmusok|< Algoritmusok]]

====== Algoritmusok bonyolultsága ======

  * **Szerző:** Sallai András
  * Copyright (c) 2014, Sallai András
  * Szerkesztve: 2014, 2017, 2022
  * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|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.

{{:oktatas:programozás:algoritmusok:nagysagrendek_2.png|}}


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ő Θ(log<sub>2</sub> n)
  * lineáris idő Θ(n)
  * n * logaritmikus idő Θ( n log<sub>2</sub> n)
  * kvadratikus idő Θ(n<sup>2</sup>)
  * faktoriális idő Θ(n!)

==== A gnuplot néhány vonatkozása ====

A log<sub>2</sub> n kifejezést néha így rövidítik: log n.

A gnuplot parancs:
<code>
plot [1:40] [-10:40] gamma(x+1), x**2, x*log(x)/log(2),x,log(x)/log(2),1
</code>

A [[https://hu.wikipedia.org/wiki/Gamma-f%C3%BCggv%C3%A9ny|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  ^  n<sup>2</sup>  ^  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(n<sup>2</sup>)
  * buborék rendezés O(n<sup>2</sup>)
  * gyors rendezés O(n<sup>2</sup>)
  * shell-rendezés O(n log<sub>2</sub> 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.

{{:oktatas:programozás:algoritmusok:nagysagrendek_legrosszabbak.png|}}

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)) | <nowiki>O(n^2)</nowiki> |
^ Buborék-rendezés | Ω(n)) | <nowiki>Θ(n^2)</nowiki> | <nowiki>O(n^2)</nowiki> |
^ Beszúrásos rendezés | Ω(n) | <nowiki>Θ(n^2)</nowiki> | <nowiki>O(n^2)</nowiki> |
^ Shell rendezés | Ω(n log(n)) | <nowiki>Θ(n(log(n))^2)</nowiki> | <nowiki>O(n(log(n))^2)</nowiki> |

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