Bonyolultságelmélet

Algoritmusok hatékonyságának összehasonlítására szolgál.

Pl. a Ta(n) vagy Tb(n) lépésszámú algoritmust választanád-e?

                Ta(n) = 1000*n + 200          Tb(n) = n^2 + 1

n = 1              1200 = 1.2us                      2 = 2 ns
n = 10            10200 = 10 us                    101 = 0.1 us
n = 100          100200 = 0.1 ms                 10001 = 0.01 ms
n = 1000     10^6 + 200 = 1ms                 10^6 + 1 = 1ms
n = 10000      ~10*10^6 = 10ms               ~100*10^6 = 100ms
n = 100000    ~100*10^6 = 0.1s                ~10*10^9 = 10s
n = 10^6          ~10^9 = 1s                ~1000*10^9 ~ 15-20 perc
n = 10^9         ~10^12 ~ 15-20 perc        ~10^9*10^9 = 10^9 s ~ 32 év

Processzor sebessége: 4GHz = 4 * 10^9 cycle / s ~pár százmillió művelet / s ~= 10^9 művelet

Észrevételek: a konstans szorzó és konstans többlet egy idő után nem számít, az érdekel, hogy a függvény hogy nő n-hez viszonyítva.

Jelölések:

O(n) = { f: N->N | létezik c, n0 > 0 úgy, hogy
         f(n) <= c * n    bármely n > n0 esetén }
     = "legfeljebb lineáris bonyolultságú függvények"

O(n^2) = { f: N->N | létezik c, n0 > 0 úgy, hogy
           f(n) <= c * n^2    bármely n > n0 esetén }
     = "legfeljebb négyzetes bonyolultságú függvények"

Theta(g(n)) = { f: N->N | létezik c1, c2, n0 > 0 úgy, hogy
                c1*g(n) <= f(n) <= c2*g(n)
                bármely n > n0 esetén }

Theta(n) = { f: N->N | létezik c1, c2, n0 > 0 úgy, hogy
             c1*n <= f(n) <= c2*n
             bármely n > n0 esetén }
         = "lineáris bonyolultságú függvények"

Megjegyzések

Gyakorlatok

Ta(n) = 1000*n + 200
Tb(n) = n^2 + 1

    Ta eleme? O(n)
    <=> létezik c, n0 > 0 úgy, hogy
        Ta(n) <= c * n    bármely n > n0 esetén
    <=> létezik c, n0 > 0 úgy, hogy
        1000*n + 200 <= c * n    bármely n > n0 esetén

        pl. c = 1001, n0 = 200

        1000*n + 200 <= 1001 * n
        200 <= n

        1000*n + 200 <= 1001 * n    bármely n > 200 esetén

        => Ta eleme O(n)
           más jelölés: Ta = O(n).

    Tb eleme O(n)?
    <=> létezik c, n0 > 0 úgy, hogy
        Tb(n) <= c * n    bármely n > n0 esetén
    <=> létezik c, n0 > 0 úgy, hogy
        n^2 + 1 <= c * n    bármely n > n0 esetén

    <=> létezik c, n0 > 0 úgy, hogy
        n + 1/n <= c     bármely n > n0 esetén

        nem lehetséges

        => Tb nem eleme O(n)

Bonyolultság leolvasása kódból

 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
71
72
73
74
75
76
77
78
79

#include <iostream>
#include <fstream>
using namespace std;

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

    // O(n)
    for (int i = 2; i < n; i++)
        cout << i;
    /*
        n       idő
        1000     20ms
        5000     ~5*20ms = 100ms
        1000000  ~20 s
    */

    // O(n^2)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cout << i + j << endl;
    /*
        n       idő     c*n^2 --> c*(5n)^2
        1000     20ms
        5000     ~25*20ms = 500ms
        1000000  ~10^6 * 20ms = 20 000s ~= 6h
    */

    // O(n^2)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cout << i+j << endl;

    // O(n)
    bool prim = n >= 2;
    for (int i = 2; i <= n/2; i++)
        if (n%i == 0)
            prim = false;


    // O(n)
    bool prim = n == 2 || (n>2 && n%2!=0);
    for (int i = 3; i <= n/2; i+=2)
        if (n%i == 0)
            prim = false;


    // O(sqrt(n))
    bool prim = n >= 2;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0)
            prim = false;
    /*
        n       idő     c*sqrt(n) --> c*sqrt(100n)
        1000     20ms
        100000   ~10*20ms
    */

    // O(log(n))
    for (int i = 1; i <= n; i = i*2)
        cout << i << endl;

    // c*log(n) ---> c*log(2n) = c *(1 + log(n))
    /*
        n       lépés
        1000      10
        100000    ~17
        1000000000 ~30
    */

    // O(log(n))
    while (n > 0) {
        cout << n;
        n = n / 2;
    }

    return 0;
}

Tulajdonságok

1. O(log_a(n)) = O(log_b(n))

Igaz, mert:
    log_a(n) = log_b(n) / log_b(a)
                = ( 1/log_b(a) ) * log_b(n)


2. Ha P(n) = a(k)*n^k + a(k-1)*n^(k-1) + ... + a(0)*n^0
            a(k) != 0
    akkor P(n) eleme Theta(n^k).

Ismert algoritmusok bonyolultsága:

                            idő            többletmemória

    bináris keresés         Theta(log(n))  Theta(1)

    két rendezett sorozat   Theta(n)       Theta(n)
    összefésülése (merge)

    prímteszt               Theta(sqrt(n)) Theta(1)

    ln.k.o.                 Theta(n)       Theta(1)
                            vagy:
                            Theta(log(n)) euklideszi alg.
                            HF. miért?

    maximum/minimumkeresés  Theta(n)       Theta(1)

    exchange sort           Theta(n^2)     Theta(1)
    bubble sort
    insertion sort
    selection sort

    mergesort               Theta(n*log(n))  Theta(n)