Summary of Rendezési és keresési algoritmusok

## Bevezetés az Algoritmusok Világába A **számítástechnika alapjaiban az algoritmusok állnak**. Egy algoritmus egy jól meghatározott, véges számú lépésből álló utasítássorozat, amely egy adott probléma megoldására szolgál. Gondoljunk rá úgy, mint egy receptre: pontosan leírja, mit kell tenni, milyen sorrendben, hogy egy kívánt eredményt érjünk el. Az algoritmusoknak **egyértelműnek, végrehajthatónak és végesnek** kell lenniük. A hatékony algoritmusok kulcsfontosságúak a modern számítógépes rendszerek működéséhez, legyen szó adatbázisok kezeléséről, weboldalak betöltéséről vagy mesterséges intelligencia alkalmazásokról. > Egy **algoritmus** egy jól meghatározott, véges számú lépésből álló utasítássorozat, amely egy adott probléma megoldására szolgál. ### Algoritmusok Hatékonysága: Időkomplexitás és O-jelölés Az algoritmusok „jóságát” gyakran a hatékonyságuk alapján ítéljük meg. Két fő szempont van: az **időkomplexitás** (mennyi időt vesz igénybe az algoritmus futása az input méretétől függően) és a **térkomplexitás** (mennyi memóriát használ fel). Ebben a cikkben elsősorban az időkomplexitásra fókuszálunk. Az időkomplexitást az **O-jelöléssel** (más néven nagyságrendi jelölés vagy aszimptotikus jelölés) fejezzük ki. Ez egy matematikai jelölés, amely az algoritmus futási idejének növekedési ütemét írja le az input méretének ($n$) függvényében, figyelmen kívül hagyva az állandó tényezőket és az alacsonyabb rendű tagokat. Az O-jelölés a legrosszabb esetre vonatkozó felső korlátot adja meg, ami különösen fontos a megbízható rendszerek tervezésénél. Did you know, hogy az O-jelölést eredetileg a számelméletben használták, és Paul Bachmann vezette be 1894-ben a "Analytische Zahlentheorie" című könyvében? Néhány gyakori O-jelölés és jelentésük: * **O(1) – Állandó idő:** Az algoritmus futási ideje független az input méretétől. Például egy tömb adott indexű elemének elérése. * **O(log n) – Logaritmikus idő:** Az algoritmus futási ideje logaritmikusan növekszik az input méretével. Ez nagyon hatékony, mivel az input méretének megduplázása csak egy kis állandó idővel növeli a futási időt. Példa: bináris keresés. * **O(n) – Lineáris idő:** Az algoritmus futási ideje arányos az input méretével. Példa: lineáris keresés, egy tömb összes elemének bejárása. * **O(n log n) – Lineáris-logaritmikus idő:** Gyakori és hatékony komplexitás rendezési algoritmusoknál. Példa: gyorsrendezés, összefésülő rendezés. * **O(n²) – Négyzetes idő:** Az algoritmus futási ideje az input méretének négyzetével arányosan növekszik. Kevésbé hatékony nagyobb inputok esetén. Példa: buborékrendezés, beillesztéses rendezés. * **O(2ⁿ) – Exponenciális idő:** Az algoritmus futási ideje exponenciálisan növekszik az input méretével. Nagyon lassú, csak kis inputokra használható. Példa: egyes brute-force problémamegoldások. * **O(n!) – Faktoriális idő:** Az algoritmus futási ideje a input méretének faktoriálisával arányosan növekszik. Rendkívül lassú, gyakorlatilag csak nagyon kis inputokra alkalmazható. Példa: utazó ügynök probléma brute-force megoldása. Az O-jelölés segít összehasonlítani az algoritmusokat és kiválasztani a legmegfelelőbbet egy adott feladathoz, különösen nagy adathalmazok esetén. > Az **O-jelölés** egy matematikai jelölés, amely az algoritmus futási idejének növekedési ütemét írja le az input méretének ($n$) függvényében, figyelmen kívül hagyva az állandó tényezőket és az alacsonyabb rendű tagokat. ### Gyakori Hibák és Tévedések az O-jelöléssel Kapcsolatban Az algoritmusok tanulmányozása során több gyakori tévedés is előfordulhat az O-jelöléssel kapcsolatban: * **Az O-jelölés félreértelmezése:** Sokan azt hiszik, hogy az $O(n^2)$ algoritmus mindig lassabb, mint az $O(n \log n)$ algoritmus. Ez igaz nagy input méretek esetén, de kis $n$ értékeknél az $O(n^2)$ algoritmus konstans tényezői miatt akár gyorsabb is lehet. Az O-jelölés az aszimptotikus viselkedést írja le, azaz mi történik, ha $n$ a végtelenhez tart. * **A legjobb, átla