menu
Algoritmusok és Adatszerkezetek I.
Bevezetés
Egy applikáció fejlesztése során számos szempontot figyelembe kell vennünk, ilyen például a biztonság, modularitás, és felhasználói élmény. Azonban ezeket a tényezőket egy másik metrika erőteljesen befolyásolhatja. A teljesítmény. A szoftverünk gyorsasága hatással lehet a felhasználói élményre, a modularitásra és a biztonságra egyaránt. Első ránézésre légből kapottnak tűnhet szóval vegyünk pár példát:

Felhasználói élmény: amennyiben az általunk készített applikáció lassú/nem reszponzív, akkor az negatív hatással lehet a felhasználó élményére. Csak képzeljük el milyen lenne, ha egy Google keresés ideje 2-3 másodpercet venne igénybe, vagy egy képszerkesztő program percek alatt lenne csak képes elforgatni egy 8K-s képet.

Modularitás: képzeljük el, hogy van egy API végpontunk. A feladata legyen egyszerű, egy adatbázisból termékeket ad vissza a kérésben kapott szűrők (paraméterek) szerint. Most képzeljük el, hogy ez az adatbázis elég nagy, több milliárd adatsorral. Senki nem fogja ezt a végpontot használni, hogyha a válaszidő kellően magas vagyis a hordozhatóságot sérti.

Biztonság: ezen nem sokat kell gondolkoznunk mivel a múltban párszor már előfordult, hogy a futásidő sebessége a biztonság rovására ment. Az egyik ilyen a TLS protokol implementációjában történt ( Lucky 13 teljes története ), ahol éppenséggel az volt a gond, hogy túl gyorsan dobták vissza a hibát. Szóval olykor a konzisztens futásidő is fontos.

Tanulság képpen azt tudjuk levonni, hogy nem árt ha egy elméleti becslést tudunk adni az algoritmusunk futásidejére.
Futásidő Elemzés
Hogyan is mérhetjük az általunk írt program futásidejét/memória használatát? Egy elég nyilvánvanló megközelítés, hogy egyszerűen mérjük le. Megnézzük egy egyszerű kicsi bemenettel és az bemenet méretét növelve megnézzük különböző konfigurációkra. Ez a megközelítés viszont nem fog nekünk egy teljes képet adni az algoritmus sebességéről/memória használatáról. Azzal, hogy véges sok értéket megvizsgálunk, nem feltétlen fogjuk látni a valós problémát, a növekedés mértékét. Ezenfelül a valós futásidőt sok tőlünk független tényező befolyásolhatja: rendszerterheltsége, silicon lottery, cache...

Tehát minket a programunk futásidejének/memória használatának növekedésének mértéke érdekel. Ehhez elsőnek definiálnunk kell a programunkhoz tartozó időfüggvényünket, amit \(T(N)\) fog jelölni. Ahol \(N\) a bemenet mérete. Az időfüggvényünket más tényezők is befolyásolhatják (például a bemenet rendezettsége), de egyenlőre tekintsünk el ettől, később majd látunk példát rá.

Tekintsük a lenti példát, ahol a maximum értéket keressük a tömbben. Csak a függvénnyel foglalkozunk a körülötte lévő sallang nem érdekes. Csak a demonstráció miatt része a kódnak. 

import math

x = [10, 3, 20, 4, 1, 12, -3, 0]

def maximum(array):
    maximum_value = -math.inf
    for element in array:
        if element > maximum_value:
            maximum_value = element
    return maximum_value

print(maximum(x))

Nézzük is meg mi történik a függvény belsejében. A 6. sorban egy érték hozzárendelés van amit 1 egységnyi idővel végbe tudunk vinni. Miért is 1? Mivel az hogy egy értéket egy változóhoz rendelünk nem függ a bemenet méretétől. Ezt követően a 7. sorban elkezdjük bejárni a tömböt, ami végig megy a tömb összes elemén. Ilyenkor feltételezni szoktuk, hogy a bementetünk mérete \(N\), mint ahogy korábban is említettem. Tehát a cilus időköltsége \(N\). A 8. sorban megnézzük, hogy a jelenlegi elem nagyobb-e mint az eddig ismert legnagyobb elem. Az összehasonlítás időköltsége is 1, de ezt \(N\)-szer elfogjuk végezni. Majd a következő sorban még egy érték adás követketkezik 1 költséggel, amit legrosszabb esetben szintén \(N\)-szer végzünk el. Végül visszaadjuk az értéket ami megint 1 költséggel végbe vihető.

Összességében az időfüggvényünk: $$T(N)=N+2$$

Növekvény
Az időfüggvényünk egyszerűnek és könnyen olvashatónak tűnik, de könnyen elfajulhat komplexebb algoritmusok esetén. Sőt mi csak a futásidő növekedésére vagyunk kíváncsiak, így sok mindent el is lehet hagyni mint azt látni fogjuk. A növekmény mértékét 3 szempont szerint vizsgálhatjuk, és a kurzus során a leggyakrabban használt az \(O(\cdot)\) lesz:
  • Legjobb eset:
    • Formálisan: \(f(n)=\omega(g(n))\), ha \(c_1\cdot g(n)< f(n)\) valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. [omega, kis omega]
      Másszóval tudunk adni egy függvény ami egy konstans szórzóra nézve SZIGORÚAN kisebb mint az időfüggvényünk.
    • Formálisan: \(f(n)=\Omega(g(n))\), ha \(c_1\cdot g(n)\leq f(n)\) valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. [omega, nagy omega]
      Másszóval tudunk adni egy függvény ami egy konstans szórzóra nézve kisebb mint az időfüggvényünk. (itt az egyenlőséget megengedjük)
  • Átlagos eset:
    • Formálisan: \(f(n)=\Theta(g(n))\), ha \(c_1\cdot g(n)\leq f(n)\leq c_2\cdot g(n)\) valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. [théta]
      Másszóval tudunk adni egy függvényt, ami 2 különböző konstans szorzóra maga közé tudja szorítani az időfüggvényünket.
  • Legrosszabb eset:
    • Formálisan: \(f(n)=o(g(n))\), ha \(f(n) < c_1\cdot g(n)\) valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. [ordó, kis ordó]
      Másszóval tudunk adni egy függvény ami egy konstans szórzóra nézve SZIGORÚAN nagyobb mint az időfüggvényünk.
    • Formálisan: \(f(n)=O(g(n))\), ha \(f(n)\leq c_1\cdot g(n)\) valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. [ordó, nagy ordó]
      Másszóval tudunk adni egy függvény ami egy konstans szórzóra nézve nagyobb mint az időfüggvényünk. (itt az egyenlőséget megengedjük)

Lentebb pár példa látható \(\Omega,\Theta,\text{ és }O\) függvényekre \(T(n)=f(n)\) feltételezett időfüggvényhez.

Időkomplexitási Osztályok
Az összehasonlítás elősegítéséhez a következő komplexitási osztályokba soroljuk az algoritmusainkat: $$1 < \log{n} < \sqrt{n} < n < n \log{n} < n^2 < n^3 < \dots < 2^n < 3^n < n! < n^n$$ Ezeket néhány gyakorlati példán keresztül is megnézzük.
Konstans Időkomplexitás
A konstans időkomplexitás (mint ahogy a neve is sugalja) fix konstans idő alatt elvégezhető. Azt fejezi ki, hogy a bemenet méretétől nem függ az algoritmus futásideje (vagy memóriaigénye). Jelölése: 1. Tekintsük a lenti példa kódot, amely két szám átlagát számolja ki.

Láthatjuk, hogy két szám összeadása \((C_0)\) 1 időegységet vesz igénybe. Hasonlóan az osztásról is elmondható \((C_1)\). Illetve az érték visszaadása is \((C_2)\). Tehát \(T(n)=C_0+C_1+C_2\). Mi csak a legrosszabb esetre leszünk kíváncsiak, vagyis \(O(C_0)+O(C_1)+O(C_2)=O(1)+O(1)+O(1)=3\cdot O(1)=O(1)\). Emlékezzünk, hogy definíció szerint \(f(n)=O(g(n))\), ha \(f(n)\leq c_1\cdot g(n)\), valamilyen \(n_0\) ponttól kezdve minden \(n\)-re. tehát \(g(n)=1\) és \(c_1=3\), így \(T(n)=O(1)\). Egyértelműen láthatjuk, hogy \(a\)-t és \(b\)-t bármire állíthatjuk a futásidő ugyanaz marad. 
def avg(a, b):
    sum_ = a + b
    avg_ = sum_ / 2
    return avg_

print(avg(3, 5))
Lineáris Időkomplexitás
Az hogy az algoritmusunk futásideje ne függjön a bemenet méretétől egy elég ritka eset. Leggyakrabban csak kiszeparált elemi műveletek esetén történik meg. Ezzel szemben a lineáris időkomplexitásra úgy tekinthetünk, hogy a bemenet méretével azonos arányban változik a futásidő. Jelőlése: \(n\). Tekintsük a lenti kódot, amely megint az átlagot számolja ki, csak a bemenet egy \(n\) hosszú tömb lesz és azon elemek átlagát adja vissza.

Első lépésben beállítjuk a sum_ változó értékét 0-ra (\(C_0\)), ez a bemenet méretétől nem függ, így konstans idő alatt elvégezhető. Ezt követően a tömbön elkezdünk végig iterálni (\(C_1\)), aminek a feltételezett hossza \(n\). Így a ciklus belseje \(n\)-szer fut le (ebben az esetben, ez a ciklus belsejétől függhet, később látunk majd erre példát). A ciklusunk belsejében egyetlen egy művelet található, ami hozzáadja a tömb elemét a sum_ változónkhoz, ez 1 időegységet vesz igénybe, amit \(n\)-szer hajtunk végre (\(C_2\)). Ezt követően már csak lekérdezzük a tömb hosszát (1 időegység), végrehajtunk egy osztást (1 időegység) és visszaadjuk az értéket (1 időegység). Vagyis \(C_3=1+1+1=3\).

Összességében az időfüggvényünk: $$T(n)=2n+4,$$ azonban mi a növekvényre vagyunk kíváncsiak, vagyis Ordóban: $$2n+4 \leq c_1\cdot g(n), c_1=3, n=4, g(n)=n \rightarrow O(n)$$ 
x = [4, 10, 2, -100, 69, 42, 100, -25]

def avg(A):
    sum_ = 0
    for number in A:
        sum_ += number
    return sum_ / len(A)

print(avg(x))
Logaritmikus Időkomplexitás
Amikor logaritmusról beszélünk 2-es alapú logaritmusról lesz szó. Első ránézésre nehéz lehet elképzelni, hogy ez hogyan kapcsolódhat egyetlen algoritmus futásidjéhez is, azonban elég intuitív ha belegondolunk abba, hogy \(if\dots else\dots\) ágakból épül fel a programunk. Egy \(if\) ág egy bináris döntés, amely eliminálja a döntés másik ágát. Ha ezzel tudjuk csökkenteni az átnézendő elemek számát akkor az logaritmikusan csökken majd. Erre egy példa a bináris keresés, aminek a feltétele, hogy a bemeneti tömbünk (amiben keresünk) rendezett legyen. A feladat, hogy visszaadjuk a keresett elem indexét vagy \(-1\)-et ha nincs benne.

Néézük is meg az algoritmust soronként.
  • A paraméterünk a tömb (A) és a keresendő érték (value).
  • 4. sorban 3 értéket állítunk be, ez konstans (\(C_0=3\)) időt vesz igénybe:
    • low: a tömb kezdőértékére mutat (bal)
    • mid: a tömb középsőértékére mutat MAJD
    • high: a tömb utolsóértékére mutat (jobb)
  • 6. sorban neki kezdünk a ciklusunknak, ami addig megy még a két szélső pointerünk meg nem egyezik. Első ránézésre nem feltétlen fog látszódni, hogy ez \(\log n\)-szer fut le, szóval erre még vissza utalunk. Amúgy az összehasonlítás konstans idejű.
  • 7. sorban beállítjuk a középső mutató értékét, ami a tömb közepére mutat. Ami egy átlagot számol alsó egész értékkel. (Az alsó egészértékre azért van szükség, hogy páratlan hosszú tömbökön is működjön az algoritmus)
  • 9. sorban megnézzük, hogy a középső érték a keresett érték-e, ha igen akkor vissza adjuk az indexet és végeztünk is.
  • Ha nem volt szerencsénk akkor a 12. sorral folytatjuk. Ahol azt nézzük meg, hogy a keresett érték kisebb-e mint a középső érték. Ha kisebb akkor a tömb jobb oldali felén nem is kell keresni. Mivel a tömbünk rendezett így ez egyértelmű, vagyis a jobb oldalt csak nagyobb értékek lennének.
    high = mid - 1
    Vagyis már csak a tömb bal felében keresünk innetől! Emiatt a felezés miatt fog a ciklus csak \(\log n\)-szer lefutni legrosszabb esetben.
  • 14. sor ugyan az mint az előző pont csak a tömb bal oldalát hagyjuk el és a jobb oldaliban keresünk.
  • 17. sor pedig csak akkor fut le ha a két szélső pointer összeért, vagyis nem volt az elem a tömbben.
$$T(n)=7\log{n}+5\leq c_1\cdot g(n), c_1=8, n=32, g(n)=\log{n}\rightarrow O(\log{n})$$ 
x = [2, 5, 10, 15, 30, 40, 200, 1000]

def binary_search(A, value):
    low, mid, high = 0, 0, len(A)-1

    while low != high:
        mid = (low + high)//2

        if A[mid] == value:
            return mid

        if value < A[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

print(binary_search(x, 5))
Kvadratikus Időkomplexitás
A kvadratikus vagy négyzetes időkomplixitás elég könnyen elképzelhető két lineáris művelet egybe ágyazásával (gondolj két \(for\) ciklusra). Jelölése: \(n^2\). Ilyen futásidővel rendelkező gyakran használt algoritmus például a vektor szorzás is. De tekintsük a lenti példa kódot, amely meg keres 1 duplikátumot a tömbben és a két pozíciót visszaadja.

  • 4. sorban elkezjdük bejárni a tömböt, ami \(n\) méretű. Így lesz egy referencia változónk, amihez tudjuk majd hasonlítani a többit.
  • 5. sorban megint elkezjük bejárni a tömböt, hogy a referencia változónkat a tömb többi eleméhez tudjuk hasonlítani.
  • Kitesszük, hogy csak akkor lesz hasonló a két érték, ha más pozíción vannak a tömbben és az értékük megeggyezik.
  • Majd vissza adjuk a pozíciót, vagy -1-et ha nincs duplikátum.
$$T(n)=2n^2 + n + 2 \leq c_1\cdot g(n), c_1=3, n=2, g(n)=n^2\rightarrow O(n^2)$$ 
x = [3, 20, 4, -10, 42, 1, 22, 177013, 42, 10]

def duplicate(A):
    for i in range(len(A)):
        for j in range(len(A)):
            if i != j and A[i] == A[j]:
                return i, j
    return -1, -1

print(duplicate(x))
Összetett Időkomplexitás
Egy algoritmus futásideje általában több ilyen primitív időkomplexitási osztály összessége lesz. Valóságban ritkán találkozunk egyszerű esetekkel. Például ha az előzőleg használt algoritmusokat kombináljuk:

Az algoritmusnak különösebb hasznossága nincs, csak demonstrációs jelleggel van itt. Szimplán eddig használt kódrészletek lettek újrahasznosítva. Mit is csinál a kód? Kitörli a tömbből az egyetlen duplikátumot, kiszámolja az átlagot, és visszaadja annak a pozícióját. Tudjuk, hogy a használt függvények növekvénye:
  • avg: \(O(n)\)
  • binary_search: \(O(\log{n})\)
  • duplicate: \(O(n^2)\)
  • del A[duplicate_indices[0]]: \(O(1)\)
így a lenti algoritmus \(O(n) + O(\log{n}) + O(n^2) + O(1)\), ami \(O(n^2)\) mivel mi a legnagyobb növekvényre vagyunk kíváncsiak. 
x = [-20, -10, -3, 3, 8, 10, 18, 24, 42, 42]

def avg(A):
    sum_ = 0
    for number in A:
        sum_ += number
    return sum_ / len(A)

def binary_search(A, value):
    low, mid, high = 0, 0, len(A)-1

    while low != high:
        mid = (low + high)//2

        if A[mid] == value:
            return mid

        if value < A[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

def duplicate(A):
    for i in range(len(A)):
        for j in range(len(A)):
            if i != j and A[i] == A[j]:
                return i, j
    return -1, -1

def combine(A):
    duplicate_indices = duplicate(A)
    del A[duplicate_indices[0]]
    avg_ = avg(A)
    position_of_avg_value = binary_search(A, avg_)
    return position_of_avg_value

print(combine(x))
Gyakorló feladatok
Határozd meg a növekvényét az alábbi függvénynek