Cvičenie 2 – Zložitosť

Ciele cvičení:

  • rozumieť usporiadavacím (triediacim) algoritmom SelectionSort a BubbleSort
  • rozumieť, čo je to asymptotická časová zložitosť a ako súvisí so „skutočným časom“ behu programov
  • rozumieť, čo je to O-notácia a Theta-notácia, a vedieť zaradiť funkciu do nejakej z „klasických“ tried zložitosti
  • vedieť analyzovať časovú zložitosť jednoduchých algoritmov

Je to usporiadané?

Naprogramujte metódu, ktorá overí, či prvky poľa celých čísel sú usporiadané od najmenšieho po najväčšie.



1
2
3
4
5
6
public class Cvicenie {



    public static boolean jeUsporiadane(int[] p) {



    }

}

Binárne vyhľadávanie

Na základe algoritmu z prednášky naprogramujte metódu, ktorá bude nerekurzívne implementovať binárne vyhľadávanie. Metóda ako parametre dostane usporiadané pole celých čísel p a hľadanú hodnotu hodnota. Výsledkom metódy nech je index políčka v poli, na ktorom sa hľadaná hodnota nachádza, alebo -1, ak sa táto hodnota v poli nenachádza.



1
2
3
public static int binarneHladajIndex(int[] p, int hodnota) {



}

Usporiadávanie ešte raz

Uvažujme triedu TriediaciAlgoritmus:



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
import java.util.Arrays;



public abstract class TriediaciAlgoritmus {



    /**

     * Aktualne usporiadavane pole

     */

    private int[] p;



    /**

     * Porovna prvky v poli na zadanych indexoch

     *

     * @return vrati zaporne cislo, ak p[idx1] < p[idx2], * 0, ak p[idx1]==p[idx2], a * kladne cislo, ak p[idx1] > p[idx2]

     */

    protected int porovnaj(int idx1, int idx2) {

        return Integer.compare(p[idx1], p[idx2]);



        /*

         * Alternativa:

         * if (p[idx1] < p[idx2]) return -1; * if (p[idx1] > p[idx2]) return 1;

         * return 0;

         */

    }



    /**

     * Vymeni prvky v usporiadavanom poli na zadanych indexoch

     */

    protected void vymen(int idx1, int idx2) {

        int pom = p[idx1];

        p[idx1] = p[idx2];

        p[idx2] = pom;

    }



    /**

     * Vypise pole

     */

    protected void vypisPole() {

        System.out.println(Arrays.toString(p));

    }



    /**

     * Usporiada prvky v poli od najmensieho po najvacsie

     *

     * @param p

     *            pole, ktoreho prvky maju byt usporiadane

     */

    public void utried(int[] p) {

        this.p = p;

        utried(p.length);

        this.p = null;

    }



    /**

     * Metoda, ktora implementuje triedenie podla urciteho algoritmu

     * @param dlzkaPola dlzka (pocet prvkov) usporiadavaneho pola

     */

    protected abstract void utried(int dlzkaPola);

}

Vytvorte triedu BubbleSort, ktorá rozširuje triedu TriediaciAlgoritmus a prekrýva abstraktnú metódu utried(int dlzkaPola) tak, aby implementovala vylepšené bublinkové triedenie. Pri implementácii využite metódy porovnaj a vymen.

Vytvorte triedu SelectionSort, ktorá rozširuje triedu TriediaciAlgoritmus a prekrýva abstraktnú metódu utried(int dlzkaPola) tak, aby implementovala triedenie výberom z prednášky.

Ďalšie úlohy:

  • Upravte triedu TriediaciAlgoritmus tak, aby ste počítali počet uskutočnených porovnaní a výmen.
  • Experimenálne porovnajte počet výmen a porovnaní pri jednotlivých algoritmoch.
  • Navrhnite vstup, pri ktorom bublinkové triedenie potrebuje najmenší možný počet operácií, a naopak vstup, kedy algoritmus potrebuje najväčší možný počet operácií pri poli veľkosti n. Experimentálne sa presvedčte o počte operácií vykonaných na týchto vstupoch.

Pre fajnšmekrov: Upravte triedu TriediaciAlgoritmus tak, aby ju išlo použiť aj na triedenie iných polí, ako sú polia celých čísel (napr. pole reálnych čísel, pole reťazcov, …)

Časová zložitosť experimentálne

Z využitím nižšie uvedeného programu nájdite najväčšie možné vstupy (hodnoty n), pre ktoré výpočet trvá do 5 sekúnd, resp. do 10 sekúnd.



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
public class Zlozitost {



    // Celkovy pocet zrealizovanych operacii

    public static int pocet = 0;



    // Elementarna operacia

    public static void operacia() {

        pocet++;

    }



    // Linearny pocet operacii v zavislosti od n

    public static void linearna(int n) {

        for (int i = 0; i < n; i++)

            operacia();

    }



    // n.log(n) pocet operacii v zavislosti od n

    public static void nlogn(int n) {

        for (int i = 0; i < n; i++)

            for (int j = 1; j < n; j = j * 2)

                operacia();

    }



    // Kvadraticky pocet operacii v zavislosti od n

    public static void kvadraticka(int n) {

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                operacia();

    }



    // Exponencialny pocet operacii v zavislosti od n

    public static void exponencialna(int n) {

        if (n <= 1) {

            operacia();

            return;

        }



        // 2^n = 2*2^(n-1)

        exponencialna(n - 1);

        exponencialna(n - 1);

    }



    public static void main(String[] args) {

        System.out.println("Zaciatok...");

        long zaciatok = System.nanoTime();



        exponencialna(35);



        long koniec = System.nanoTime();

        System.out.println("Cas behu: " + ((koniec - zaciatok) / 1000000)

                + " milisekund");

    }

}
    • Ak umožníme bežať programu namiesto 5 sekúnd dvojnásobný čas, t.j. 10 sekúnd, o koľko väčší vstup (hodnotu n) vieme spracovať?
    • Implementujte metódu, ktorej časová zložitosť bude „približne“ logaritmická – Ɵ(log(n)).
    • Implementujte metódu, ktorej časová zložitosť bude „približne“ logaritmická – n.log2(n) – Ɵ(log2(n)).
    • Pre fajnšmekrov: Implementujte metódu, ktorej časová zložitosť bude „približne“ faktoriál – Ɵ(n!).

Analýza zložitosti algoritmov

Určte presný počet operácií sčítania, ktoré vykoná metóda sucet, ak je vstupom pole s n prvkami.



1
2
3
4
5
6
7
8
public static int sucet(int[] p) {

    int vysledok = 0;



    for (int i = 0; i < p.length; i++)

        vysledok = vysledok + p[i];



    return vysledok;

}

Určte presný počet porovnaní, ktoré vykoná metóda pocetInverzii, ak je vstupom pole s n prvkami.



1
2
3
4
5
6
7
8
9
public static int pocetInverzii(int[] p) {

    int vysledok = 0;

    for (int i = 0; i < p.length; i++)

        for (int j = i + 1; j < p.length; j++)

            if (p[j] < p[i])

                vysledok++;



    return vysledok;

}

O a Omega notácie

  • Formálne dokážte, že 2.n = O(n).
  • Formálne dokážte, že 3.n+10 = O(n) a tiež, že 3.n+10 = Omega(n)
  • Formálne dokážte, že n2 – 2.n = O(n2)
  • Formálne dokážte, že pre ľubovoľné funkcie f, g a h platí:
    • Ak f = O(g) a g = O(h), potom f = O(h)
    • Ak f = O(h) a g = O(h), potom f + g = O(h)
    • Interpretujte tieto matematické tvrdenia v kontexte analýzy časovej zložitosti algoritmov.
  • Usporiadajte nasledujúce funkcie tak, aby platilo, že ak f je pred g, potom f = O(g)
    • n!, 1000.n2 + 30.n, 20.log(n), 2.n.log(n), n + 10000000000000
    • Vybrané časti formálne dokážte
  • Je pravdou, že počet porovnaní v metóde pocetInverzii je:
    • O(n3)
    • O(n2)
    • O(n)
  • Je pravdou, že počet operácií sčítania je v každom algoritme riešiacom tento problém je Omega(n) ?

Analyzuj to!

Analyzujte jednotlivé metódy. Čo počítajú a aká je ich asymptotická časová zložitosť? Snažte sa o čo najtesnejšie ohraničenie časovej zložitosti.



1
2
3
4
5
6
7
8
9
public static boolean rovnake3(int[] p) {

    for (int i = 0; i < p.length; i++)

        for (int j = i + 1; j < p.length; j++)

            for (int k = j + 1; k < p.length; k++)

                if ((p[i] == p[j]) && (p[j] == p[k]))

                    return true;



    return false;

}





1
2
3
4
5
6
7
8
9
10
11
12
13
public static int zaujimavySucet(int[] p) {

    int vysledok = 0;

    int pocet = p.length;



    for (int i = 0; i < p.length; i++) {

        for (int j = 0; j < pocet; j++)

            vysledok = vysledok + p[j];



        pocet = pocet / 2;

    }



    return vysledok;

}





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int rozdel(int p[]) {

    int pivot = p[0];

    int left = 0;

    int right = p.length - 1;



    while (left <= right) {

        while ((left <= right) && (p[left] <= pivot))

            left++;



        while ((left <= right) && (p[right] > pivot))

            right--;



        if (left < right) {

            int pom = p[left];

            p[left] = p[right];

            p[right] = pom;

        }

    }



    return left;

}

Na zamyslenie:

  • Vedeli by ste preprogramovať metódu rovnake3 tak, aby vrátila ten istý výsledok, ale mala asymptoticky lepšiu časovú zložitosť?

Pre fajnšmekrov:



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
public static int umocni1(int a, int n) {

    int vysledok = 1;

    for (int i = 0; i < n; i++)

        vysledok = vysledok * a;



    return vysledok;

}



public static int umocni2(int a, int n) {

    if (n == 0)

        return 1;



    return a * umocni2(a, n - 1);

}



public static int umocni3(int a, int n) {

    if (n == 0)

        return 1;



    if (n % 2 == 0) {

        int vysledok = umocni3(a, n / 2);

        return vysledok * vysledok;

    } else {

        int vysledok = umocni3(a, (n - 1) / 2);

        return a * vysledok * vysledok;

    }

}

Vedeli by ste napísať nerekurzívnu verziu metódy umocni3?

Asymptotická analýza časovej zložitosti

Cieľom prednášky bolo nielen intuitívne ukázať, v čom spočíva asymptotická analýza časovej zložitosti, ale aj načrtnúť, prečo je to celé takto vymyslené a aká matematika sa za tým skrýva.

O čom to vlastne celé je? (zjednodušenie zjednodušenej verzie)

Máme nejaký algoritmus. Cieľom analýzy časovej zložitosti je zrátať počet krokov (elementárnych inštrukcií), ktoré algoritmus vykoná. Zvyčajne nás zaujíma len horné ohraničenie počtu vykonaných krokov v závislosti od veľkosti vstupu (napr. veľkosť poľa, počet čísel na vstupe, atď). Teda hľadáme takú funkciu T(n), že

  • algoritmus na vstupe veľkosti n nikdy nespraví viac ako T(n) krokov,
  • existuje taký vstup veľkosti n, že algoritmus spraví presne T(n) krokov (T(n) sa už nedá zmenšiť).

Nájsť „dobrú“ funkciu T(n) pre zadaný algoritmus je veľmi náročná úloha. Ale:

  • na multiplikatívnych a aditívnych konštantách v informatike často veľmi nezáleží,
  • je náročné odhadnúť úplne presný počet krokov skrývajúcich sa za jednotlivými časťami zápisu algoritmu (vzhľadom na predošlý bod je veľká šanca, že to aj tak nikoho nezaujíma),
  • pekný analytický zápis funkcie T(n) nemusí existovať,
  • zaujíma nás len miera rastu – ako veľmi s veľkosťou vstupu rastie počet vykonaných krokov algoritmu na danom vstupe.

Dôsledkom toho je, že pri asymptotickej analýze časovej zložitosti (=zaujíma nás, čo sa deje, keď veľkosť vstupu n rastie do nekonečna) nám namiesto presnej T(n) postačí len funkcia f(n) taká, že T(n) = O(f(n)). Navyše chceme, aby f(n) sa čo najviac približovala T(n). Lebo kto má vo svojom algoritme menšiu f(n), ten „vyhráva“. No a nepohneváme sa, keď tá funkcia f(n) aj bude nejako „pekná“ (v jednoduchosti je krása). Inými slovami, hľadáme čo „najmenšiu“ funkciu f(n), že existuje nejaké číslo c, že počnúc nejakým n0 (=od istého n), bude presný počet krokov algoritmu T(n) menší ako c*f(n).

Kto má asymptoticky tesnejšie ohraničenie počtu vykonaných krokov?

Nech T(n) = f(n) a T(n) = g(n). Ak f(n) = O(g(n)) a g(n) != O(f(n)), potom f(n) je „tesnejšie“ ohraničenie počtu krokov než g(n).

Jednoduché odhady

Veľmi často vieme presný počet krokov algoritmu ohraničiť tak, že „pozrieme na mieru navnáranosti“ cyklov. Príkladom je rovnake3. Ale je takéto ohraničenie „tesné“ – neexistuje „tesnejšie“ asymptotické ohraničenie? V prípade rovnake3 sa dá formálne ukázať, že žiaden asymptoticky „tesnejší“ odhad nie je. Treba si však dávať pozor na metódy ako zaujimavySucet, kde odhadovanie zložitosti cez „navnáranosť“ cyklov síce nejaké asymptotické ohraničenie dá, no nebude tesné – teda vieme nájsť oveľa „menšiu“ funkciu, ktorá asymptoticky zhora ohraničuje počet vykonaných krokov algoritmu.

Farebné kroky

S komplexnosťou algoritmov rastie náročnosť analýzy časovej zložitosti – teda určenia presného počtu krokov vykonaných algoritmom. Niekedy pomôže nasledovná finta: Ofarbime si každý vykonaný krok algoritmu jednou z dvoch farieb – napr. červenou alebo modrou. Farby jednotlivých krokov sa môžu všelijako striedať – ale každý krok má len jednu farbu. Farba môže zodpovedať príkazom nejakej metódy alebo istej činnosti. Nech C(n) je počet červených krokov a M(n) je počet modrých krokov. Zjavne C(n) + M(n) = T(n). Z jednej z úloh vyššie vyplýva, že ak C(n) = O(f(n)) a M(n) = O(f(n)), potom aj C(n) + M(n) = T(n) = O(f(n)). Vďaka tejto jednoduchej finte môžeme rozložiť analýzu časovej zložitosti algoritmu na niekoľko menších analýz (samostatne analyzujeme počet červených krokov a samostatne počet modrých krokov). Túto fintu je možné zovšeobecniť aj na viac farieb.