Podcast
Questions and Answers
Mi az algoritmus futási ideje?
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?
Melyek a futási idejének típusai az algoritmusoknak?
Milyen esetben mondjuk legjobb és legrosszabb esetnek?
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 __.
A legjobb eset futási ideje __.
Signup and view all the answers
A legrosszabb eset futási ideje __.
A legrosszabb eset futási ideje __.
Signup and view all the answers
Hogyan definiáljuk a nagy ordót (O(g(n)))?
Hogyan definiáljuk a nagy ordót (O(g(n)))?
Signup and view all the answers
Az Omega (Ω) jelölés alulról korlátos függvényeket jelöl.
Az Omega (Ω) jelölés alulról korlátos függvényeket jelöl.
Signup and view all the answers
Kapcsold össze a függvényeknek a növekedési rendszerintjét az azokat jelölő jelölésekkel.
Kapcsold össze a függvényeknek a növekedési rendszerintjét az azokat jelölő jelölésekkel.
Signup and view all the answers
Mi a Rekurzió a számítástechnikában?
Mi a Rekurzió a számítástechnikában?
Signup and view all the answers
Mi az a partíció a számításelméletben?
Mi az a partíció a számításelméletben?
Signup and view all the answers
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.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
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.
