1 of 26

Algoritmusok futásidő elemzése�2024.09.18

2 of 26

Előző órai példák

Szám (kártya) kitalálása? (Bináris keresés)
Sátor keresése?

3 of 26

Előző órai példák

n elemű rendezett vektorba egy elem megkeresése?
Egy adott (rendezetlen) tömbben elem megtalálása?
Szekvenciális/Soros keresés

4 of 26

Miért fontos ez a gyakorlatban?

Az algoritmusok futásidő elemzése és az idő- és memóriaigények fontos szerepet játszanak az iparban és a számítástechnikában.

5 of 26

Miért fontos ez a gyakorlatban?

Itt van néhány életszerű példa arra, hogy miért fontosak ezek az elemek:

Kereskedelmi weboldalak teljesítmény optimalizálása (ezer termék szűrése)
Mobil alkalmazások hatékonysága (rosszul optimalizált algoritmus == eszköz lassulhat)
Adatbázis lekérdezések gyorsítása (idő és memóriaigény elemzése)
Gyártási folyamatok optimalizálása (idő és memóriaigény elemzése)
Rendszerbiztonság és kibertámadás elleni védelem (brute force időigénye)
Autonóm járművek és robotok (azonnali döntéseket)

6 of 26

Időigény

7 of 26

Hogyan vizsgálunk időigényt?

Az időigény függ az inputtól: például egy már rendezett tömböt könnyebben lehet rendezni, mint egy nem rendezettet.

Függ az input hosszától: egy nagy tömbben hosszabb ideig tart egy elem megkeresése, mint egy rövidebben.

Általában jobban szeretünk egy garantált felső korlátot mondani az időigényre.

8 of 26

Az időigény analízis további fajtái

A legrosszabb eset, ha egy algoritmus időigénye T(n), ha az algoritmus tetszőleges n méretű inputon T(n) időben megáll.

Átlagos eset: T(n) = az algoritmus várható időigénye az összes lehetséges n méretű bemeneten.

Legjobb eset: olyan eset, ahol az amúgy lassú algoritmus néhány speciális inputra mégis gyors

9 of 26

Az időigény analízis további fajtái

10 of 26

Az időigény analízis további fajtái

Hogyan számítjuk ki egy algoritmus legrosszabb eset időigényét?

Miközben nem akarjuk kiszámolni precízen a függvényt …

NAGY ÖTLET: ¨ Nézzük csak azt, hogy milyen gyorsan nő a T(n), ha n → ∞.

11 of 26

A lépesszám pontos meghatározása helyett általában elegendő a lepésszám nagyságrendjének meghatározása, ebből már (kis óvatossággal) lehet következtetni arra, hogy az algoritmus mennyire hatékony.

12 of 26

Ezzel már elég jól megtudjuk jósolni, hogy ha nagyobb bemenetre akarjuk az algoritmusunkat használni, akkor mennyivel fog tovább dolgozni.

Például tegyük fel, hogy egy program az n0 = 20 méretű teszteseteken 6 másodpercig fut.

Meddig fog futni, egy n1 = 400 = 20n0 méretű bemeneten?

13 of 26

Jelölje f(n) az algoritmus maximális lépésszámát az n hosszú bemeneteken.
Nézzünk néhány esetet:

14 of 26

Nézzünk néhány esetet:

15 of 26

16 of 26

Abdul Bari

time complexity

17 of 26

Példák

13n + 8 = T(?)
2n² + 87n + 369 = T(?)
9n³+ 2n² + 87n + 369 = T(?)
85 log₃n + 17 = T(?)
85 log₁₀n + 17 = T(?)
85 log₁₀n + 17n = T(?)

18 of 26

Példák

13n + 8 = T(n)
2n² + 87n + 369 = T(n²)
9n³+ 2n² + 87n + 369 = T(n³)
85 log₃n + 17 = T(log n)
85 log₁₀n + 17 = T(log n)
85 log₁₀n + 17n = T(n)

Példák Θ-ra

19 of 26

Időigény

Akarunk készíteni egy programot amely összeadja egy tömb elemeit.

[1, 22, 51, 8, 7, …….,85]

Hogyan számítjuk ki egy algoritmus legrosszabb eset időigényét?

Miközben nem akarjuk kiszámolni precízen a függvényt …

20 of 26

Időigény

NAGY ÖTLET: ¨ Nézzük csak azt, hogy milyen gyorsan nő a T(n), ha n → ∞.

21 of 26

given_array = [1,4,3,2,………,10]

def find_sum(given_array):

total = 0

for each i in given_array:

total = total +i

return total

O(1)

T = O(1) + n*O(1) + O(1)

T = c4+ n*c5 = O(n)

O(1)

22 of 26

T = O(1) + nx(nxO(1)) + O(1)

23 of 26

2x{

?????

24 of 26

2x{

25 of 26

Esetleg….valaki megszeretné kérdezni, hogy ezt miért kell tanulni?

26 of 26

Ajánlott linkek

Videók:

Linkek: