Cvičenia: 2. týždeň

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.

public class Cvicenie {

        public static boolean jeUsporiadane(int[] p) {

        }
}
[$[Get Code]]

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.

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

}
[$[Get Code]]

Usporiadávanie ešte raz

Uvažujme triedu TriediaciAlgoritmus:

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 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);
}
[$[Get Code]]

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.

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");
        }
}
[$[Get Code]]
  • 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" n.log2(n) - Ɵ(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.

public static int sucet(int[] p) {
        int vysledok = 0;

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

        return vysledok;
}
[$[Get Code]]

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

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;
}
[$[Get Code]]

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.

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;
}
[$[Get Code]]
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;
}
[$[Get Code]]
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;
}
[$[Get Code]]

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:

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;
        }
}
[$[Get Code]]

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