1. tétel Flashcards
(16 cards)
Kupacrendezés
Az A tömbre meghívjuk a buildheap eljárást, amely kupac tulajdonságúvá változtatja a kupacot. A kupacrendezés a gyökérelemet (amely a legnagyobb) az utolsó helyre teszi felcseréléssel, kiveszi azt a kupacból, a többi elemre helyreállítja a kupactulajdonságot és ugyanúgy folytatja az algoritmust a többi elemre rendezve.
O(n log(n)) nem stabil
Gyorsrendezés
A gyors rendezés során az eredeti tömböt két résztömbre osztjuk. Az egyik résztömb egy kulcs (pivot) elemnél nem nagyobb, a másik résztömb pedig a nagyobb elemeket tartalmazza. Ha elvégezzük a két résztömb rendezését, akkor a rendezett résztömbök egymáshoz fűzésével az eredeti tömböt kapjuk vissza rendezve. Természetesen a résztömbök rendezését is meg kell oldani valahogy, amit ismét két-két még kisebb résztömbre osztással végezhetjük el. Ez a kisebb tömbökre való partícionálás egészen addig folytatható, amíg egy elemű résztömböket kapunk.
legr: O(n^2); O(n log(n)) nem stabil
Összefésülő rendezés
Az összefésülő rendezés alapötlete, hogy eleve rendezett elemsorozatok aránylag egyszerűen vonhatók össze rendezett sorozattá. Az algoritmus lényege, hogy az elemeket két csoportba osztjuk, a csoportokat rendezzük (akár összefésülő rendezéssel), majd a kapott részeket összefésüljük.
O(n log(n)) stabil
Beszúró rendezés
Elindulunk a tömb elejétől a vége felé, és ha a soron következő nem illeszkedik a már kialakult sorrendbe, akkor kiemeljük. Addig tologatjuk a tőle balra lévő elemeket jobbra, amíg azok nagyobbak nála, vagy már nincs több elem. Az így felszabaduló helyre beszúrjuk a kiemelt elemet. A következő ciklusban mindig egyel magasabb pozícióról indulva ismételten elvégezzük a vizsgálatot, amíg ki nem alakul a megfelelő sorrend.
legj: Omega(n); O(n^2) stabil
Minimumkiválasztó rendezés
Megkeresi a rendezetlen tömbrészlet legkisebb elemét, és az elejére rakja. (CSAK PAKOL)
O(n^2) stabil
Buborék rendezés
Mindig két szomszédos elemet hasonlít össze, ha kell, megcseréli őket.
legj: Omega(n); O(n^2) stabil
Leszámláló rendezés
Minden elemnél meghatározza a nála kisebb elemek számát (így a vizsgált elem közvetlenül a saját pozíciójába kerülhet a kimeneti tömbben, kivétel, ha a tömb egyforma elemeket is tartalmaz). Egy n hosszúságú A tömbbe rakjuk az elemeket, majd ezeket egy C tömb segítségével sorrendbe rendezzük a B kimeneti tömbbe.
O(n+k) stabil
Edény rendezés
Az edény rendezés esetén abból indulunk ki, hogy ha sikerül az elemeket egymástól (sorrendben) elkülönülő csoportokba osztani, akkor az egyes csoportok rendezése után azok rendezett sorozattá fűzhetők össze. Az edényekbe szétosztjuk az elemeket, mindegyik edényben egy listát kezelve. Az azonos edényben lévőket (pl.: beszúró módszer szerint) rendezzük, majd a listákat a végén összefűzzük az elsővel kezdve.
O(n) stabil
Nagy ordó
Felülről korlátos függvény
Definíció: Egy adott g(n) függvény esetén O(g(n))-nel (olvasd: „ordó g(n)” vagy „nagy ordó
g(n)”) jelöljük a függvényeknek azt a halmazát, amelyre O(g(n)) = {f(n) : létezik c és n0 pozitív
állandó úgy, hogy 0 ≤ f(n) ≤ cg(n) teljesül minden n ≥ n0 esetén}
Nagy ómega
Alulról korlátos függvény
Definíció: Egy adott g(n) függvény esetén Ω(g(n))-nel (kiejtve „ómega g(n)” vagy „nagy ómega
g(n)”) jelöljük a függvényeknek azt a halmazát, amelyre Ω(g(n)) = {f(n) : létezik c és n0 pozitív
konstans úgy, hogy 0 ≤ cg(n) ≤ f(n) teljesül minden n ≥ n0 esetén
Nagy théta
Alul felül korlátos függvény
Definició: Egy adott g(n) függvény esetén Θ(g(n))-nel jelöljük a függvényeknek azt a halmazát,
amelyre Θ(g(n)) = {f(n) : létezik c1, c2 és n0 pozitív állandó úgy, hogy 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
teljesül minden n ≥ n0 esetén}.
Legjobb, legrosszabb és átlagos futási idők
Adott x bemenetre jelölje 𝑇(𝐴, 𝑥) az A algoritmus tényleges futási idejét, ami az x bemeneti adatra ténylegesen végrehajtott elemi műveletek futási idejének az összege. Jelölje |x| az x bemeneti adat méretét.
- Legjobb futási idő: 𝑇𝑙𝑗(𝐴, 𝑛) = min{𝑇(𝐴, 𝑥) | |𝑥| = 𝑛}
- Legrosszabb futási idő: 𝑇𝑙𝑗(𝐴, 𝑛) = max{𝑇(𝐴, 𝑥) | |𝑥| = 𝑛}
- Átlagos futási idő: 𝑇𝑎(𝐴, 𝑛) = ∑|𝑥|=𝑛 𝑃𝑟(𝑥)𝑇(𝐴, 𝑥), ahol Pr (𝑥) annak a valószínűsége, ha x bemeneti adata lesz az A algoritmusnak.
Lineáris keresés
- Nem rendezett tömbben való elemek megtalálására szolgál.
- A tömb elemeit sorra vesszük, míg az adott elem nem egyenlő a kívánt elemmel.
- Legrosszabb futási idő: Ο(𝑛) (a futási idő a tömb méretével lineárisan nő)
- Legjobb futási idő: Ο(𝑛/2)
Logaritmikus (bináris) keresés
- Rendezett tömbben való elemek megtalálására szolgál.
- Vesszük a tömb közepén lévő értéket. Ha a keresett elem kisebb, mint az érték, akkor az elemtől jobbra lévő résztömböt levágjuk. Ha a keresett elem nagyobb, mint az érték, akkor az elemtől balra lévő résztömböt vágjuk le. Ez így folytatódik, míg meg nem találjuk a keresett elemet.
- Legrosszabb futási idő: Ο(log(𝑛))
- Legjobb futási idő: Ο(log(𝑛))
- Átlagos futási idő: Ο(log(𝑛))
Közvetlen kiválasztás
- Megkeresi a sorban a következő legkisebb elemet és az adott elemmel felcseréli
O(n^2) stabil
Számjegyes rendezés
- A leszámláló rendezés kiterjesztése.
- Azonos hosszúságú szavak, számjegyek és dátumok esetén alkalmazható.
- Elsőként a legkisebb helyiértékű számjegyek alapján növekvő sorrendbe rendezzük őket, majd a második legkevésbé értékessel, míg végül eljutunk a legértékesebb jegyig.
