algoritmus
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
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"
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
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)
Az algoritmusok hatékonyságát az alábbi szempontok alapján értékelhetjük:
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:
Az algoritmus által elfoglalt memória mérete a bemenet nagyságának függvényében.
Ezek az algoritmusok egy lista elemeinek meghatározott sorrendbe állítására szolgálnak.
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 > lista: lista, lista = lista, lista return lista
Hatékonyabb rendezési algoritmus ((O(n n)) átlagosan).
python def gyors_rendezes(lista): if len(lista) <= 1: return lista pivot = lista kisebb = egyenlo = nagyobb = return gyors_rendezes(kisebb) + egyenlo + gyors_rendezes(nagyobb)
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
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 == cel: return kozep elif lista < cel: bal = kozep + 1 else: jobb = kozep - 1 return -1
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 = 0 prioritas_sor = while prioritas_sor: akt_tav, akt_csucs = heapq.heappop(prioritas_sor) if akt_tav > tavolsag: continue for szomszed, suly in graf: uj_tav = akt_tav + suly if uj_tav < tavolsag: tavolsag = uj_tav heapq.heappush(prioritas_sor, (uj_tav, szomszed)) return tavolsag
A perzsa al-Khwārizmī (الخَوَارِزْمِيّ (al-ḵawārizmiyy) névből.