Tartalom

1. Elméleti alapok
   • Elemi lépés fogalma
   • A bemenet mérete
   • Legrosszabb, átlagos és legjobb esetek
   • Melyik algoritmus a jobb?
   • Bonyolultságosztályok
   • Néhány gyakran alkalmazott tétel
2. Becslések a gyakorlatban
   • Bonyolultság leolvasása kódból
   • Feladatban elvárt bonyolultság megállapítása

1. Elméleti alapok

Hatékonynak nevezünk egy algoritmust, ha kevés erőforrás (pl. idő és memória) felhasználásával oldja meg azt a feladatot, amire tervezték.

Az algoritmusok hatékonyságának vizsgálatakor egy bonyolultságelmélet (complexity theory) nevű tudományág lesz a segítségünkre. Ennek eszközeivel viszonylag könnyen tudunk becsléseket adni az általunk leírt algoritmusok idő és memóriaigényére.

Először a futásidővel fogunk foglalkozni, azonban az itt bemutatott fogalmak ugyanúgy alkalmazhatók a memóriahasználat kérdésére is.

1.1. Elemi lépés fogalma

A mai processzorok olyan digitális áramkörök, melyeket egy órajel vezérel. Ennek frekvenciája határozza meg, hogy másodpercenként hányszor aktiválódik a processzor és végez valamilyen műveletet vagy annak egy részét. Például egy 2 GHz-es órajellel rendelkező processzor másodpercenként 2 milliárdszor aktiválódik.

A különböző elvégezhető műveletek különböző számú aktiválódási cikluson át tartanak. Hogy pontosan melyik mennyi ideig, az függ a processzorarchitektúrától, vagy akár konkrét modellek mikroarchitek- túrájától, a műveletek hardveres megvalósítási módjától. Például egy összeadás vagy kivonás számára lehet, hogy egy-két ciklus is elég, egy szorzáshoz kellhet 4, egy osztáshoz több tíz, egy RAM-műveletre pedig (olvasás vagy írás) akár 100-nál több cikluson át is várhatunk.

Ezekkel a részletekkel az algoritmusok készítésekor általában nem akarunk foglalkozni (esetleg csak nagyon sajátos helyzetekben). Ezért a továbbiakban elemi lépésnek, vagy egyszerűen csak lépésnek fogunk nevezni egy olyan elemi műveletet (vagy azok néhány darabját), amit a processzor egyszerre (vagy majdnem egyszerre) el tud végezni.

Persze ez az egyszerűsítés egy jelentős hátránnyal jár együtt: nem tudjuk megmondani, hogy pontosan mennyi ideig tart egy lépés, mert egyik tarthat akár tízszer annyi ideig, mint a másik. Ennek ellenére a lépések számával fogunk csak foglalkozni a továbbiakban és ez elég jó becslésekre ad majd lehetőséget. Ha ezeknél pontosabbat szeretnénk mondani, akkor általában a futásidő mérésére hagyatkozunk majd.

1.2. A bemenet mérete

Tekintsünk egy egyszerű algoritmust: meg szeretnénk állapítani adott sorozat elemeinek átlagát (az elemek száma adott).

Egy lehetséges megvalósítás:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    double s = 0;

    for (int i = 1; i <= n; i++) {
        int szam;
        cin >> szam;

        s = s + szam;
    }

    cout << s / n << endl;

    return 0;
}

Hány lépést kell végezzen ez az algoritmus?

Beolvassuk az elemek számát, inicializáljuk az s és i változókat (3 lépés). Ezt követően minden elem esetén (azaz minden iterációban) a for ciklus végez egy-egy összehasonlítást és léptetést, a benne levő kód pedig egy-egy beolvasást és összeadást (4-4 lépés elemenként). A végén még szükség van egy összehasonlításra (ami miatt leáll a for ciklus), majd egy osztásra és egy kiírásra (3 lépés).

Hány lépés ez összesen? Attól függ, hogy hány eleme van a sorozatnak és ez az „attól függ”, ez a legtöbb algoritmus során megjelenik.

Tehát egy algoritmus lépésszáma a bemenet méretétől függ (és ezt általában n-nel jelöljük majd a továbbiakban). Itt a bemenet mérete alatt érthetjük a számok lehető legnagyobb értékét (ha csak egy-két szám a bemenet), egy sorozat hosszát (ez a tipikus), vagy akár egy szám bitjeinek számát is az alkalmazási terület függvényében.

Az előbbi példában az általunk becsült lépésszám 3 + 4*n + 3 = 4*n + 6.

Olyan helyzet is előfordulhat, hogy a bemenet méretét két számmal célszerűbb leírni mint eggyel. Például két eltérő hosszú sorozat feldolgozásakor (hosszaikat jelölheti N és M) vagy egy gráf esetén, ahol a pontok és élek száma különböző nagyságrendű lehet.

1.3. Legrosszabb, átlagos és legjobb esetek

Az előbbiekben láttuk, hogy a lépésszám függ a bemenet méretétől. De nem csak a mérete számít…

Tekintsük például a következő feladatot: adott n, majd egy n elemű sorozat, írjuk ki minden páratlan elem esetén annak összes osztóját!

Itt már nem csak az számít, hogy milyen hosszú a sorozat, hanem az is, hogy hány páratlan eleme van (mivel a páratlan elemekkel jóval több dolgunk van mint a párosakkal).

Ha futásidő szempontjából vizsgáljuk az algoritmust adott n esetén, akkor a legjobb az, ha nincs egyetlen páratlan eleme sem (ilyenkor elég beolvasni, és ellenőrizni az elemek paritását). A legrosszabb eset viszont az, ha minden elem páratlan (ekkor minden elemre valamilyen módon fel kell sorolni annak osztóit is).

A lépésszám becslésekor általában csak a legrosszabb esettel foglalkozunk. Ennek oka, hogy ha valamilyen korlátunk van, akkor abba még a legrosszabb esetben is be akarunk férni. Ez a korlát lehet egy versenyfeladat időlimitje vagy akár valamilyen a valóságból származó fizikai megkötés (pl. egy 20 FPS-es animáció esetén két-két képkocka között csak 50ms idő áll rendelkezésünkre az összes számítás elvégzésére a következő képkockához).

Esetenként szokás az átlagos esetet és ennek a lépésszámát is vizsgálni (pl. quicksort). Az előbbi példában átlagos eset az lenne, ha az elemeknek nagyjából a fele páros, viszont nem mindig ennyire egyszerű eldönteni, hogy mi számít átlagosnak (vagy hogy átlagoljuk az összes lehetséges bemenetet).

1.4. Melyik algoritmus a jobb?

Tegyük fel, hogy adott feladatot két különböző algoritmussal is meg tudunk oldani, és hogy valamilyen úton pontosan meg tudtuk határozni ezek lépésszámát a legrosszabb esetben.

Legyen az A algoritmus lépésszáma egy n hosszú bemenet esetén: TA(n) = 1000 * n + 200, a B algoritmusé pedig TB(n) = n^2 + 1 (a ^ itt a hatványozást jelöli, tehát TB(n) = n * n + 1).

Vizsgáljuk meg, hogy különböző nagyságrendű n-ek esetén hány lépést végeznek ezek az algoritmusok:

Kis bemenetekre (n = 1000-ig) a B algoritmus lépésszáma a kisebb, nagy bemenetekre pedig az A algoritmusé. Melyik algoritmus a jobb? (Ha például nincs lehetőségünk mindkettőt implementálni és n függvényében vagy az egyiket, vagy a másikat használni, hanem csak egyet implementálhatunk, akkor melyiket válasszuk?)

Próbáljuk meg ezeket a lépésszámokat időbecslésre lefordítani. Tegyük fel, hogy egy gyors számítógépünk van, ami másodpercenként százmillió (azaz 10^8) lépést elvégez (a gyakorlatban jelenleg – 2026 tájékán – ez egy elfogadható feltevés: annak függvényében, hogy milyen lépésekről van szó általában több tízmillió vagy százmilliónyi lépést is el tudunk végezni a mai több GHz-es processzorok egy-egy magján).

Az előbbi táblázat számadatait tehát szorozni fogjuk ezzel a 1/10^8 lépés/s értékkel, hogy megkapjuk a becsült futásidőket:

A táblázatban ns a nanoszekundum (10^-9 s), us pedig a mikroszekundum (10^-6 s).

Látszik, hogy bár kis bemenetekre a B algoritmus jobb, az A algoritmus sem fut túl sok ideig, nagy bemenetekre viszont a B algoritmus sokkal rosszabb és a futásidők különbsége már érezhetővé válik.

Tehát ha választani kell (mondjuk egy rögzített egy másodperces időkorlát mellett), akkor az A algoritmust választjuk, mert az nagyobb n-ekre is le tud még futni egy másodperc alatt.

1.5. Bonyolultságosztályok

Tekintsük ismét az előző részben vizsgált két lépésszámfüggvényt:

    TA(n) = 1000 * n + 200
    TB(n) = n^2 + 1

Az vizsgálat adataiból néhány következtetést le tudunk vonni:

• hiába volt az A algoritmusban legalább 200 lépés n-től függetlenül, a B-ben meg csak egy darab, nagy n-ekre ez már nem számított (tehát a konstans lépéstöbblet nem volt releváns).
• hiába volt az A algoritmus lépésszámában az n-t tartalmazó tag együtthatója 1000 a B algoritmus esetén pedig csak 1, mert nagy n-ek esetén nem ez számított, hanem, hogy az n^2 értéke n-nél sokkal nagyobbra nő (és gyorsabban); tehát a konstans szorzóbeli különbség sem volt releváns

Mivel a lépésszám amúgy sem adná meg pontosan a futásidőt, ezért annak pontos ismerete nem lesz szükséges. Csak az fog érdekelni a továbbiakban, hogy a lépésszám hogyan nő az n növekedésével.

Például az A algoritmus esetén ha valamilyen n-re 5 másodperc a futásidő, akkor egy kétszer nagyobb n esetén 10 másodpercre számítunk majd (vagyis ahányszorosára nő az n, annyiszorosára nő a futásidő). Ez azért van, mert nagy n-ek esetén TA(2*n) = 1000 * (2*n) + 200 ≈ 2 * (1000 * n + 200) = 2 * TA(N), a konstans többlet kétszerezésétől itt eltekintettünk.

A B algoritmus esetén viszont, ha adott n-re 5 másodperc a futásidő, akkor egy kétszer nagyobb n esetén TB(n) = (2*n)^2 + 1 = 4 * n^2 + 1 ≈ 4 * (n^2 + 1) = 4 * TB(n), vagyis lépésszám (és ezzel együtt a futásidő nagyjából a négyszeresére nő).

Tehát az fog számítani, hogy a lépésszámfüggvények n-től függő része mennyire gyorsan nő az n növekedésével. Ennek pontosítására bevezetjük a következő jelöléseket (függvény-halmazokat):

    O(g(n)) = { f : N -> N | léteznek a pozitív c és n0 konstansok úgy, hogy:
        f(n) ≤ c · g(n)  bármely n ≥ n0 esetén
    }

Sajátosan például:

    O(n) = { f : N -> N | léteznek a pozitív c és n0 konstansok úgy, hogy:
        f(n) ≤ c · n  bármely n ≥ n0 esetén
    }
    
    O(n²) = { f : N -> N | léteznek a pozitív c és n0 konstansok úgy, hogy:
        f(n) ≤ c · n²  bármely n ≥ n0 esetén
    }
    
    O(1) = { f : N -> N | léteznek a pozitív c és n0 konstansok úgy, hogy:
        f(n) ≤ c  bármely n ≥ n0 esetén
    }

Angolul ezt big-O notationnek szokták hívni.

Néhány észrevétel:

• O(g(n))-be tartozik minden olyan függvény, ami nem nő gyorsabban, mint a g(n), azaz tetszőleges általunk választott c konstanssal megszorozva a g(n)-t elérhető, hogy az az f(n) fölött maradjon;
• nem érdekel, hogy kicsi n-ekre hogy viselkedik a függvény, elég ha egy általunk megválasztott n0 küszöbérték fölött igaz a leírásban megadott feltétel.

Példák:

Az előbbi algoritmusok esetén TA ∈ O(n), mert létezik például c = 1001, n0 = 200 úgy, hogy TA(n) ≤ 1001 · n bármely n ≥ 200 esetén (1000 · n + 200 ≤ 1001 · n). Hasonlóan belátható, hogy TB ∈ O(n²), legyen c = 2 és n0 = 1.

TA ∈ O(n²) is teljesül, legyen c = 1001, n0 = 200, mint az O(n)-es érvelésnél.

Viszont TB ∉ O(n), mert akárhogy választanánk c és n0 konstansokat, TB(n) ≤ c · n ⟺ n + 1/n ≤ c ⟹ n ≤ c, ami nem lehet igaz tetszőleges n ≥ n0 esetén.

Másik jelölés, ami más alsó korlátot is tartalmaz (ha esetleg zavarna, hogy TA egyszerre van O(n)-ben és O(n²)-ben is):

    Θ(g(n)) = { f : N -> N | léteznek a pozitív c1, c2 és n0 konstansok úgy, hogy:
        c1 · g(n) ≤ f(n) ≤ c2 · g(n)  bármely n ≥ n0 esetén
    }

Fogjuk még a Theta(g(n)) jelölést is használni a Θ(g(n)) halmazra (hogy ne kelljen mindig görög betűt írni gépelés közben).

Sajátosan például:

    Θ(n) = { f : N -> N | léteznek a pozitív c1, c2 és n0 konstansok úgy, hogy:
        c1 · n ≤ f(n) ≤ c2 · n  bármely n ≥ n0 esetén
    } - ez a "lineáris bonyolultságú függvények" halmaza
    
    Θ(n²) = { f : N -> N | léteznek a pozitív c1, c2 és n0 konstansok úgy, hogy:
        c1 · n² ≤ f(n) ≤ c2 · n² bármely n ≥ n0 esetén
    } - ez a "négyzetes bonyolultságú függvények" halmaza
  
    Θ(1) = { f : N -> N | léteznek a pozitív c1, c2 és n0 konstansok úgy, hogy:
        c1 ≤ f(n) ≤ c2  bármely n ≥ n0 esetén
    } - ez a "konstans lépésszámú függvények" halmaza

Néhány tulajdonság, ami azonnal következik az értelmezésekből (a bizonyításukat az olvasóra bízzuk):

• Theta(g(n)) ⊆ O(g(n)) bármely g(n) függvény esetén
• Theta(konstans · n) = Theta(n), illetve O(konstans · n) = O(n)
• Theta(n + konstans) = Theta(n), illetve O(n + konstans) = O(n)

Ennek megfelelően például az O(2·n) jelölést nem szoktuk használni, helyette O(n)-t írunk (mert a két halmaz azonos).

Az f ∈ O(g(n)) jelölés helyett gyakran írjuk egyszerűen azt, hogy f = O(n) (bár szigorú értelemben nem egyenlőségről van szó, a jobb oldalon ugyanis egy függvényhalmaz van).

1.6. Néhány gyakran alkalmazott tétel

Az alábbiak könnyen bizonyíthatók az értelmezésekből:

1. tétel:

Az összegeknek csak a domináns (leggyorsabban növekvő) tagja számít.

Legyen például f = O(n), g = O(n^2). Ekkor (f+g) = O(n^2).

2. tétel:

A polinomoknak csak a fokszáma számít (ez az előző tétel következménye).

Legyen f(n) = a(k) * n^k + a(k-1) * n^(k-1) + … + a(1) * n + a(0) valamilyen k és a(i) konstansok esetén. Ekkor f = Theta(n^k).

Példák:

• n^2 + 5n - 2 = Theta(n^2),
• n^3 + 100n = Theta(n^3),
• n*(n-1)/2 = Theta(n^2).

3. tétel:

A logaritmusoknak nem számít az alapja.

Ha log_x(y)-nal jelöljük az y szám x alapú logaritmusát, akkor írhatjuk, hogy O(log_a(n)) = O(log_b(n)) bármely a, b logaritmusalapok esetén.

Ez azért van így, mert az alapcsere képletben csak egy konstans szorzó jelenik meg: log_a(n) = log_b(n) * log_a(b).

Mivel az alap nem számít, ezért a logaritmikus bonyolultságot általában csak O(log(n))-nel jelöljük.

2. Becslések a gyakorlatban

Az időbonyolultság (nagyságrendileg hány lépést végzünk) vagy memóriabonyolultság (nagyságrendileg hány bájt memóriát használunk) megállapítása (legalább a bonyolultságosztályok szintjén) segít eldönteni, hogy a vizsgált erőforrásigény milyen növekedésére számíthatunk majd nagyobb bemenetek esetén, mint amilyenekkel a programot teszteltük (és esetleg pontos méréseket is végeztünk ezekre).

2.1. Bonyolultság leolvasása kódból

Lássunk néhány példát, n-t tekintjük most a bemenet méretének:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
using namespace std;

int main()
{
    int n;
    // ...

    // 1.
    for (int i = 0; i <= n; i++) {
        cout << i;
    }
    // Ez Theta(n) idő, mert van 1 darab kezdőértékadás,  n+1 darab cout és növelés, 
    // illetve n+2 darab ellenőrzés.
     
    // ...

    // 2.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << i+j;
        }
    }
    // Ez Theta(n^2), mert ennyiszer történik meg a cout (a többi művelet pedig 
    // vagy ugyanennyiszer, vagy kevesebbszer).

    // ...

    // 3.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cout << i+j;
        }
    }
    // 1 + 2 + 3 + ... + n = n(n+1)/2 = 1/2 * n^2  + 1/2 * n
    // Szintén Theta(n^2).

    // ...

    // 4.
    for (int i = 1; i*i <= n; i++) {
        cout << i;
    }
    // Ez Theta(sqrt(n)), mert az i értéke sqrt(n)-ig tud nőni.

    // ...

    // 5.
    for (int i = 1; i*i <= n; i+=5) {
        cout << i;
    }
    // Szintén Theta(sqrt(n)), bár a háttérben levő konstans az előző ötöde.

    // ...

    // 6.
    for (int i = 1; i <= n; i *= 2) {
        cout << i;
    }
    // 1 kör után i = 2
    // 2 kör után i = 4
    // ....
    // k kör után i = 2^k
    //
    // Leállás előtt mindig: 2^k <= n  <=>  k <= log2(n)
    //
    // Tehát a lépésszám Theta(log(n)).

    return 0;
}

2.2. Feladatban elvárt bonyolultság megállapítása

Rendszerint úgy számolunk, hogy a lépésszám másodpercenként ne haladja meg a százmilliót (10^8-t), de a tízmilliós nagyságrend még biztonságosabb.

Példák:

• időlimit 1s, N ≤ 2000: ekkor O(N), O(N^2), O(N^2 * log(N)) belefér az időbe, O(N^3) már nem;
• időlimit 1s, N ≤ 10000: ekkor O(N), O(N^2) belefér az időbe, O(N^2 * log(N)) vagy O(N^3) már nem;
• időlimit 1s, N ≤ 100000: ekkor O(N), O(N * log(N)), O(n * sqrt(N)) belefér az időbe, O(N^2) már nem;
• időlimit 0.1s, N ≤ 10000: ekkor O(N), O(N * log(N)), O(n * sqrt(N)) belefér az időbe, O(N^2) már nem.

A memóriával hasonlóan járunk el, például N = 5000-re még lehet, hogy van O(N^2) memóriánk (bár ez már a száz MB-os nagyságrendben mozog), de N = 100000 esetén már biztosan nincs. A memóriahasználatot viszont a bonyolultságosztályoknál pontosabban is megtervezhetjük a legtöbb feladat esetén (leszámítva esetleg a kódszegmens által okozott konstans többletet), például egy 100 x 100-as int mátrix 40KB helyet foglal.