10 Questions
Mi az algoritmus futási ideje?
Az algoritmus futási ideje egy program végrehajtásához szükséges idő.
Melyek a futási idejének típusai az algoritmusoknak?
Átlagos eset
Milyen esetben mondjuk legjobb és legrosszabb esetnek?
Legjobb esetben a leghamarabb végződő esetet, legrosszabb esetben a legtöbb időt igénylő esetet jelenti.
A legjobb eset futási ideje __.
n+1
A legrosszabb eset futási ideje __.
2n
Hogyan definiáljuk a nagy ordót (O(g(n)))?
Az O(g(n)) egy adott függvény olyan halmazát jelöli, amelyre létezik pozitív állandó és n0, hogy a függvényérték mindig az alsó határérték és a sokszorosa között van.
Az Omega (Ω) jelölés alulról korlátos függvényeket jelöl.
True
Kapcsold össze a függvényeknek a növekedési rendszerintjét az azokat jelölő jelölésekkel.
Legjobb eset futásideje = n+1 Legrosszabb eset futásideje = 2n Alulról korlátos függvény = Ω(g(n)) Felülről korlátos függvény = O(g(n)) Alul felül korlátos függvény = Θ(g(n))
Mi a Rekurzió a számítástechnikában?
Az objektum definícióját rekurzívnak nevezzük, ha a definíció tartalmazza a definiálandó objektumot.
Mi az a partíció a számításelméletben?
Partíció a természetes számok összegre való felbontását jelenti.
Study Notes
Algoritmus futási ideje
- Az algoritmus futási ideje egy program végrehajtásához szükséges idő.
- A futási idő erősen függ a futtató számítógéptől, a használt környezettől és fordítótól.
- Az algoritmus futási idejének jellemzéséhez gyakran használjuk a nagy O jelölést.
Szélső esetek
- Az algoritmusok futási idejének vizsgálatakor fontos a lehetséges legkisebb és legnagyobb futási idő meghatározása.
- A legjobb eset ideje a legkedvezőbb futási idő, a legrosszabb eset ideje a legkedvezőtlenebb futási idő.
Aszimptotikus jelölések
- Az O jelölés nagy ordó, azaz felülről korlátos függvény.
- Az Ω jelölés nagy ómega, azaz alulról korlátos függvény.
- A Θ jelölés theta, azaz alul-felül korlátos függvény.
Rendezési algoritmusok
- Rendezési algoritmusok: kupacrendezés, gyorsrendezés, buborék rendezés, rendezés minimum kiválasztással, rendezés közvetlen kiválasztással, beszúró rendezés, összefésülő rendezés, leszámláló, számjegyes rendezés, edény rendezés.
- A rendezési algoritmusoknak két fő típusa van: az összehasonlító és a nem összehasonlító rendezések.
Rendező algoritmusok
- Kupacrendezés (Heapsort): O(n * log(n)) futási idő, stabil rendezés.
- Gyorsrendezés (Quicksort): átlagos esetben O(n * log(n)) futási idő, stabil rendezés, de legrosszabb esetben O(n^2).
- Buborék rendezés: O(n^2) futási idő, nem stabil rendezés.
- Összefésülő rendezés: O(n * log(n)) futási idő, stabil rendezés.
- Számláló rendezés (Counting sort): Θ(n + k) futási idő, csak egész számok halmazán vett értékekre működik.
- Számjegyes rendezés: lineáris futású rendezés, azonos hosszúságú szavak, stringek rendezésére használható.
- Edény rendezés: lineáris futású rendezés, 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.
Kereső algoritmusok
- Lineáris keresés: O(n) futási idő, legrosszabb esetben O(n).
- Logaritmikus keresés (Bináris keresés): O(log(n)) futási idő, rendezett tömbben keres.
A quiz a számítástudományban használt algoritmusokról szól, beleértve a futási idejüket és a különböző rendező algoritmusokat.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
