algorithmic efficiency (tsz. algorithmic efficiencies)
A algoritmikus hatékonyság (algorithmic efficiency) azt vizsgálja, hogy egy adott algoritmus milyen erőforrásokat használ fel (idő, memória, stb.) egy probléma megoldása során. Ez a számítástechnika egyik legfontosabb elemző szempontja, mert segít meghatározni, melyik algoritmus gyorsabb, takarékosabb vagy praktikusabb egy adott feladat megoldásához.
Az algoritmikus hatékonyság egy algoritmus idő- és/vagy tárhelyigényének jellemzése, különösen a bemenet méretének függvényében.
| Típus | Mit mér? | Példa |
|---|---|---|
| Időkomplexitás | Mennyi idő alatt fut le az algoritmus? | O(n), O(n log n) |
| Térkomplexitás | Mennyi memóriát használ fel? | O(1), O(n²) |
| Energiafogyasztás | Mobil vagy beágyazott rendszerek esetén is fontos | |
| I/O-műveletek száma | Nagy fájlok esetén kritikus lehet |
Ez a jelölés az algoritmus viselkedését írja le nagy bemenetek esetén.
| Jelölés | Név | Példa algoritmus |
|---|---|---|
| O(1) | Konstans idő | Lista első elemének elérése |
| O(log n) | Logaritmikus idő | Bináris keresés |
| O(n) | Lineáris idő | Lista bejárása |
| O(n log n) | Lineáris-logaritmikus | Gyorsrendezés (quick sort) |
| O(n²) | Kvadratikus idő | Buborékrendezés |
| O(2ⁿ) | Exponenciális idő | Naiv Fibonacci rekurzió |
| O(n!) | Faktoriális idő | Permutációk kipróbálása (brute-force TSP) |
1. Naiv keresés
def contains(lst, value):
for item in lst:
if item == value:
return True
return False
→ O(n) idő
2. Bináris keresés (rendezett listán)
def binary_search(lst, value):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst == value:
return True
elif lst < value:
low = mid + 1
else:
high = mid - 1
return False
→ O(log n) idő
gprof, valgrind, cProfile)
| Ok | Miért számít |
|---|---|
| Teljesítmény | Nagy adathalmazokon csak hatékony algoritmusok futnak jól |
| Skálázhatóság | Egy rossz komplexitású algoritmus gyorsan használhatatlanná válik |
| Energia- és erőforrás-takarékosság | Mobil vagy beágyazott rendszerek esetén különösen fontos |
| Jobb felhasználói élmény | Gyorsabb válaszidő, reszponzív alkalmazások |
Az algoritmikus hatékonyság az algoritmus viselkedésének mértéke a futási idő és erőforrás-felhasználás szempontjából. Segítségével meghatározható, hogy melyik algoritmus a legalkalmasabb egy adott probléma megoldására, különösen nagy bemeneti méretek esetén. Ez a programozás és algoritmuselmélet egyik alapköve, és elengedhetetlen a magas teljesítményű, optimalizált szoftverek készítéséhez.