Ugrás a tartalomhoz

algoritmus

A Wikiszótárból, a nyitott szótárból

Magyar

Kiejtés

  • IPA: [ ˈɒlɡoritmuʃ]

Főnév

algoritmus

  1. (matematika, informatika, számításelmélet, algoritmusok) Az algoritmus egy probléma megoldására szolgáló, pontosan meghatározott lépések sorozata, amelyet egy gép (például számítógép) vagy ember követhet. Az algoritmusok az informatika és a matematika alapvető fogalmai közé tartoznak, és kulcsszerepet játszanak a programozásban, valamint a különböző problémák hatékony megoldásában.


Algoritmusok főbb jellemzői

  1. Végesség: Az algoritmus véges számú lépés után befejeződik.
  2. Egyértelműség: Az egyes lépések pontosan meghatározottak és félreérthetetlenek.
  3. Bemenet: Az algoritmus rendelkezhet bemeneti adatokkal, amelyek a probléma kezdeti állapotát reprezentálják.
  4. Kimenet: Az algoritmus legalább egy eredményt (kimenetet) ad vissza.
  5. Hatékonyság: Az algoritmusnak az adott erőforrások (idő és memória) szempontjából optimálisnak kell lennie.


Algoritmusok típusai

  1. Lineáris algoritmusok
    Olyan algoritmusok, amelyek egyenes vonalban, lépésről lépésre hajtják végre az utasításokat.
    Példa: Egy számokból álló lista elemeinek összege.

    def osszeg(lista):
    osszeg = 0
    for szam in lista:
        osszeg += szam
    return osszeg

  2. Elágazó algoritmusok
    Ezeknél az algoritmusoknál a végrehajtás iránya a feltételek teljesülésétől függ.
    Példa: Egy szám pozitív, negatív vagy nulla.

    def szam_tipusa(szam):
    if szam > 0:
        return "Pozitív"
    elif szam < 0:
        return "Negatív"
    else:
        return "Nulla"

  3. Ismétlődő algoritmusok (Iteráció)
    Egy algoritmus bizonyos lépései ismétlődnek egy adott feltétel teljesüléséig.
    Példa: Faktoriális számítása.

    def faktorialis(n):
    eredmeny = 1
    for i in range(1, n + 1):
        eredmeny *= i
    return eredmeny

  4. Rekurzív algoritmusok
    Az algoritmus önmagát hívja meg egy kisebb részprobléma megoldására.
    Példa: Fibonacci-számok kiszámítása.

    def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


Algoritmusok hatékonysága

Az algoritmusok hatékonyságát az alábbi szempontok alapján értékelhetjük:

  1. Időbonyolultság (Time Complexity):

Az algoritmus futásához szükséges idő a bemenet méretének függvényében. Az időbonyolultságot gyakran Big-O jelöléssel adjuk meg:

    • (O(1)): Konstans idő.
    • (O(n)): Lineáris idő.
    • (O(n^2)): Négyzetes idő, például a buborékrendezés esetében.
    • (O(n)): Logaritmikus idő, például bináris keresésnél.
  2. Térbonyolultság (Space Complexity):

Az algoritmus által elfoglalt memória mérete a bemenet nagyságának függvényében.


Példák különböző algoritmusokra

1. Rendezési algoritmusok

Ezek az algoritmusok egy lista elemeinek meghatározott sorrendbe állítására szolgálnak.

  • Buborékrendezés (Bubble Sort):

Egyszerű, de nem túl hatékony algoritmus ((O(n^2))).
python def buborek_rendezes(lista): n = len(lista) for i in range(n): for j in range(0, n-i-1): if lista[j] > lista[j+1]: lista[j], lista[j+1] = lista[j+1], lista[j] return lista

  • Gyorsrendezés (Quick Sort):

Hatékonyabb rendezési algoritmus ((O(n n)) átlagosan).
python def gyors_rendezes(lista): if len(lista) <= 1: return lista pivot = lista[len(lista) // 2] kisebb = [x for x in lista if x < pivot] egyenlo = [x for x in lista if x == pivot] nagyobb = [x for x in lista if x > pivot] return gyors_rendezes(kisebb) + egyenlo + gyors_rendezes(nagyobb)

2. Keresési algoritmusok

  • Lineáris keresés

Egyszerű, de lassú algoritmus ((O(n))).
python def linearis_kereses(lista, cel): for i, elem in enumerate(lista): if elem == cel: return i return -1

  • Bináris keresés

Hatékonyabb, ha a lista rendezett ((O(n))).
python def binaris_kereses(lista, cel): bal, jobb = 0, len(lista) - 1 while bal <= jobb: kozep = (bal + jobb) // 2 if lista[kozep] == cel: return kozep elif lista[kozep] < cel: bal = kozep + 1 else: jobb = kozep - 1 return -1

3. Graf-algoritmusok

  • Dijkstra algoritmus

Rövid legútdetektálás egy csúcsról a gráfban.
python import heapq def dijkstra(graf, kezd): tavolsag = {csucs: float('inf') for csucs in graf} tavolsag[kezd] = 0 prioritas_sor = [(0, kezd)] while prioritas_sor: akt_tav, akt_csucs = heapq.heappop(prioritas_sor) if akt_tav > tavolsag[akt_csucs]: continue for szomszed, suly in graf[akt_csucs]: uj_tav = akt_tav + suly if uj_tav < tavolsag[szomszed]: tavolsag[szomszed] = uj_tav heapq.heappush(prioritas_sor, (uj_tav, szomszed)) return tavolsag


Etimológia

A perzsa al-Khwārizmī (الخَوَارِزْمِيّ‎ (al-ḵawārizmiyy) névből.

Fordítások

Lásd még

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=algoritmus&oldid=3479434”