Adatstrukt 04 Algoritmus futási ideje Flashcards
(10 cards)
Mit jelent a nagy O jelölés (Big O)?
A legrosszabb eset futási idejének felső korlátját adja meg.
Mit jelent a nagy Omega jelölés (Ω)?
Az algoritmus futási idejének alsó korlátját mutatja meg (legjobb eset).
Mit jelent a nagy Théta jelölés (Θ)?
A futási idő pontos korlátját jelzi (átlagos eset).
Mi a lineáris keresés legjobb és legrosszabb esete?
Legjobb: O(1), legrosszabb: O(n).
Mi a bináris keresés futási ideje?
Legrosszabb esetben O(log n), legjobb esetben O(1), ha az első próbálkozás talál.
Milyen algoritmus tartozik a lineáris idejű rendezésekhez?
Counting Sort, Radix Sort, Bucket Sort.
Mely algoritmusok négyzetes időigényűek?
Insertion Sort, Selection Sort, Bubble Sort.
Mi a gyorsrendezés (Quick Sort) átlagos és legrosszabb futási ideje?
Átlagos: O(n log n), legrosszabb: O(n²).
Mi jellemző a kupacrendezésre (Heap Sort)?
Minden esetben O(n log n) időben működik.
Mi jellemző az összefésüléses rendezésre (Merge Sort)?
Stabil, és minden esetben O(n log n) futási idejű.
