1. Úvod

Priebeh semestra

Vyučovanie počas semestra sa skladá z

  • týždenne jedna dvojhodinová prednáška
  • týždenne jedno dvojhodinové cvičenie
  • skoro každý týždeň jedno domáce zadanie
  • jeden semestrálny projekt
  • jeden písomný test
  • praktická skúška pri počítači

cvičenia

prebiehajú v počítačových halách H3 a H6

  • bude sa precvičovať látka hlavne z prednášky v danom týždni
  • môžete pracovať na vlastnom notebooku
  • spolupráca na cvičeniach nie je zakázaná - je odporúčaná
    • môžete pracovať aj po dvojiciach (dvaja riešia úlohy pri jednom počítači)
  • na cvičeniach je povinná aktívna účasť
    • budú sa kontrolovať vyriešené úlohy
    • riešenie budete ukladať na úlohový server LIST
  • povolené sú maximálne 2 absencie

domáce zadania

počas semestra dostanete niekoľko povinných samostatných domácich zadaní

  • na ich vyriešenie dostanete väčšinou 2 až 3 týždne
  • vaše riešenia budú bodované (väčšinou 10 bodov)
    • maximálny počet bodov získate len za úplne správne riešenie
    • riešenie budete ukladať na úlohový server LIST

riešenia musíte vypracovávať samostatne - spolupráca je zakázaná

priebežné hodnotenie

aktívna účasť na cvičeniach a body získané za domáce zadania sú priebežným hodnotením semestra

  • zo všetkých cvičení počas semestra môžete mať maximálne 2 neúčasti
  • zo všetkých domácich zadaní musíte získať spolu aspoň 50% bodov
  • ak nesplníte podmienky priebežného hodnotenia, získavate známku Fx (bez možnosti robiť skúšku)

semestrálny projekt

v priebehu semestra dostávate možnosť riešiť jeden semestrálny projekt:

  • tému si zvolíte sami, mala by obsahovať niečo, čo je obshom nášho predmetu ADŠ
  • ideálne je robiť jeden projekt v C++, ktorý je vhodný pre predmet Programovanie (3) aj ADŠ
  • za načas odovzdaný projekt môžete získať maximálne 10 bodov - body nad 5 sa pripočítavajú k bodom ku skúške (ak máte aspoň 5 bodov, započítavajú sa ku skúške)
  • pri splnení podmienky ročníkového projektu, sa tento projekt môže hodnotiť aj ako ročníkový projekt

skúška

sa skladá z dvoch častí:

  1. písomný test (posledný týždeň semestra 17.12.) - max. 40 bodov
  2. praktická skúška pri počítači (v skúškovom období) - max. 60 bodov
  • máte nárok na 2 opravné termíny

hodnotenie skúšky

spočítajú sa body z písomného testu, praktickej skúšky, príp. bodov za semestrálny projekt:

  • :-) známka A 88 bodov
  • :-) známka B 81 bodov
  • :-) známka C 74 bodov
  • :-) známka D 67 bodov
  • :-) známka E 60 bodov
  • :-( známka Fx menej ako 60 bodov

Analýza algoritmov

Časová zložitosť

Budeme skúmať rôzne algoritmy z pohľadu ich rýchlosti behu pre rôzne veľké vstupné údaje. Už z programovania v prvom ročníku máme nejaké skúsenosti, že niektoré programy sú pre veľké vstupy veľmi pomalé, niekedy sa dokonca ani nedočkáme výsledkov. Zatiaľ boli naše úvahy skôr intuitívne. Teraz sa zoznámime so základmi posudzovania časovej zložitosti rôznych skupín algoritmov.

Ukážeme to na riešení takejto úlohy: v danom číselnom poli potrebujeme zistiť počet všetkých dvojíc rovnakých hodnôt. Pozrime si takéto jednoduché riešenie:

pole = [2, 6, 7, 5, 4, 7, 8, 3, 1, 5, 9]
n = len(pole)
pocet = 0
for i in range(n):
    for j in range(i + 1, n):
        if pole[i] == pole[j]:
            pocet += 1
print(pocet)

Uvedomte si, aký bude výsledok pre pole rovnakých hodnôt, napr. pre pole = [1, 1, 1, 1, 1].

Poďme teraz odmerať, ako dlho bežal tento program. Urobíme to tak, ako sme to robili v prvom ročníku. Jednou z možností je merať čas pre rôzne veľké náhodné polia:

for n in range(1000, 10001, 1000):
    pole = [random.randrange(n) for i in range(n)]
    tim = time.time()
    pocet = 0
    for i in range(n):
        for j in range(i + 1, n):
            if pole[i] == pole[j]:
                pocet += 1
    tim = time.time() - tim
    print(n, round(tim, 3))

Z nameraných hodnôt môžeme nakresliť napr. takýto graf:

graf závislosti času od veľkosti vstupných údajov

Zrejme si uvedomujete, že takéto merania nie sú presné, ale za to aspoň vidíme, ako tento odmeraný čas rastie.

Skúsme to urobiť inak. Program nebudeme spúšťať, len budeme počítať. Budeme počítať počet elementárnych inštrukcií, ktoré sa vykonajú pre pole veľkosti n. Predpokladajme, že tieto operácie majú približne rovnaký jednotkový čas:

  • priradenie do premennej prem = hodnota
  • zistenie hodnoty premennej prem
  • vykonanie aritmetickej operácie hodnota1 op hodnota2
  • porovnanie dvoch hodnôt hodnota1 rel hodnota2
  • zaindexovanie prvku poľa prem[hodnota]
  • volanie funkcie
  • návrat z funkcie

Tiež predpokladajme, že for-cyklus:

for i in range(n):
    telo_cyklu

sa pre zjednodušenie bude prepisovať takto:

i = 0                       # 1 inštrukcia
while i < n:                # 2 inštrukcie
    #telo_cyklu
    i += 1                  # 1 inštrukcia

Poďme teraz počítať telo vnútorného cyklu:

if pole[i] == pole[j]:      # 5: i, pole[i], j, pole[j], ==
    pocet += 1              # 3: pocet, pocet+1, pocet = hodnota

Telo vnútorného cyklu bude trvať 5 alebo 8 časových jednotiek, podľa výsledku porovnania. Keďže sa toto vykonáva vo for-cykle, pripočítajme k tomuto času 2 jednotky na začiatok a jednu na koniec. Takže telo cyklu je 8 alebo 11 jednotiek za každý prechod.

Prepíšme oba for-cykly:

pocet = 0                            # 1
i = 0                                # 1
while i < n:                         # 2
    j = i + 1                        # 3
    while j < n:                     # 2
        if pole[i] == pole[j]:       # 5
            pocet += 1               # 3
        j += 1                       # 1
    i += 1                           # 1

Vnútorný for-cyklus sa bude vykonávať najprv. pre i=0, potom pre i=1, potom pre i=2, atď. až naposledy pre i=n-1, teda prvýkrát pôjde n-2 krát, potom n-3 krát, … až 1-krát. Spolu je to súčet: 1 + 2 + 3 + … + n-2, teda (n-1)*(n-2)/2. Budeme predpokladať najhorší prípad (časovo najnáročnejší), teda že telo vnútorného cyklu beží 11 časových jednotiek. Vonkajší for-cyklus (teda while) beží n krát, teda n krát sa vykoná test i<n aj i+=1.

Celkový čas potom:

f(n) = (n-1)*(n-2)/2 * 11 + n * 6 + 2 = 5.5 * n ** 2 - 16.5 * n + 6 * n + 3

Takúto funkciu, ktorá vyjadruje časový odhad trvania nejakého konkrétneho algoritmu, budeme nazývať časová zložitosť. Pravdepodobne, keby sme nakreslili priebeh tejto funkcie, dostali by sme veľmi podobné výsledky ako graf v našich prvých meraniach.

V skutočnosti nás nebude zaujímať až taký presný vzorec (s nepresnými predpokladmi o trvaní jednotlivých inštrukcií), ale dôležitý bude charakter takejto funkcie, teda či rastie rýchlo, či rastie rovnako ako funkcia iného algoritmu, alebo či rastie pomalšie ako iná funkcia.

V prvom rade budeme zanedbávať všetky „nepodstatné“ konštanty. Na priebeh funkcie to nemá skoro žiaden vplyv. Tiež, ak sa nejaká funkcia skladá z viacerých členov, pričom jeden rastie rýchlejšie a iný pomalšie, tak ten pomalší tiež „zanedbáme“. Teda pre náš algoritmus je dôležité, že jeho časová zložitosť je kvadratická funkcia (rastie tak rýchlo, ako n**2).

Triedy funkcií veľké O( )

Funkcie časovej zložitosti budeme zaraďovať do tried. Každá z tried bude charakteristická nejakou funkciou, ktorá ju ohraničuje zhora.

Formálnejšie musí platiť:

  • funkcia f(n) patrí do tej istej triedy ako g(n), ak existuje číselná konštanta c, že pre dosť veľké n platí c * g(n) >= f(n)
  • takúto triedu funkcií potom označujeme O(g(n)) (hovoríme trieda veľké O)
  • budeme hovoriť, že f(n) patrí do O(g(n)), alebo aj f(n) je O(g(n))

Funkcii g(n) sa hovorí horný asymptotický odhad funkcie f(n).

Napr. časová zložitosť nášho skúmaného programu je O(n**2).

Formálne

Pre dané dve funkcie f(n) (odhad počtu elementárnych inštrukcií algoritmu) a g(n) hovoríme, že f(n) je triedy O(g(n)), ak existujú také dve kladné konštanty c a n0, že pre každé n > n0 platí:

c * g(n) >= f(n)

Môžete si predstaviť napr. takto:

grafy funkcií g(n) a f(n)

Základné skupiny funkcií časovej zložitosti

V tomto kurze sa budeme stretávať len s týmito skupinami funkcií:

O(1) konštantná zložitosť

Algoritmus, ktorý nezávisí od veľkosti vstupu. Napr. ak chceme zistiť súčet radu čísel od 1 do n a poznáme na to vzorec:

def sucet(n):
    return n * (n+1) // 2

O(log n) logaritmická zložitosť

Časová zložitosť je logaritmická funkcia, napr. hľadanie prvku v utriedenom poli algoritmom binárne vyhľadávanie:

def hladaj(hodnota, pole):
    od, do = 0, len(pole)
    while od <= do:
        stred = (od + do) // 2
        if pole[stred] == hodnota:
            return True
        if pole[stred] < hodnota:
            od = stred + 1
        else:
            do = stred - 1
    return False

Uvedomte si, že pri logaritmickej funkcii nemusíme špecifikovať základ logaritmov, nakoľko platí

logA n = logB n / logB A

pre ľubovoľné základy A a B.

O(n) lineárna zložitosť

Algoritmus, ktorého zložitosť rastie lineárne s veľkosťou vstupu. Napr. ak chceme zistiť súčet radu čísel od 1 do n a počítame to pomocou cyklu:

def sucet(n):
    res = 0
    for i in range(1, n+1):
        res += i
    return res

Ale tiež hľadanie hodnoty v neutriedenom poli:

def hladaj(hodnota, pole):
    for prvok in pole:
        if prvok == hodnota:
            return True
    return False

O(n log n) zložitosť n * log n

Neskôr budeme vidieť, že najrýchlejšie algoritmy triedenia poľa s prvkami ľubovoľných typov má práve túto zložitosť. Dokonca ukážeme, že ani nemôže neexistovať algoritmus s lepšou zložitosťou.

O(n**2) kvadratická zložitosť

Časová zložitosť je kvadratická funkcia, napr. bublinkové triedenie:

def tried(pole):
    for i in range(len(pole)):
        for j in range(len(pole)-1):
            if pole[j] > pole[j+1]:
                pole[j], pole[j+1] = pole[j+1], pole[j]

O(n**3) kubická zložitosť

Algoritmy s touto zložitosťou sú zriedkavejšie ako kvadratické, ale uvidíme ich napr. pri riešení grafových úloh.

O(2**n) exponenciálna zložitosť

Veľmi často sú to algoritmy prehľadávania s návratom (backtracking), v ktorých prechádzame všetky vygenerované možnosti a vyberáme niektoré podľa nejakých kritérií. Najčastejšie sú to rekurzívne algoritmy.

Podobne ako pri logaritmických zložitostiach aj do tejto triedy patria funkcie s ľubovoľným základom.

O(n!) faktoriálová zložitosť

Napr. rekurzívne vygenerovanie všetkých permutácií:

def generuj(i):
    for j in range(n):
        if not bolo[j]:
            pole[i] = j
            bolo[j] = True
            if i == n - 1:
                print(pole)
            else:
                generuj(i + 1)
            bolo[j] = False

n = 3
pole = [0] * n
bolo = [False] * n
generuj(0)

Porovnanie

Zrejme medzi týmito triedami zložitosti platí takýto vzťah:

**O(1)** < **O(log n)** < **O(n)** < **O(n log n)** < **O(n**2)** < **O(n**3)** < **O(2**n)** <  **O(n!)**

Ako si zjednodušiť zisťovanie časovej zložitosti

  1. postupnosť príkazov, v ktorej je každý O(1), má zložitosť O(1)
  2. for-cyklus s n-prechodmi, ktorý vykonáva len O(1), má zložitosť O(n)
  3. všeobecnejšie for-cyklus s n-prechodmi, ktorý vykonáva telo cyklu O(f), má zložitosť O(n * f)
  4. while cyklus, ktorý znižuje (zvyšuje) nejakú testovanú premennú o konštantu, má zložitosť O(n * f), kde O(f) je telo cyklu, n je testovaná hodnota
  5. while cyklus, ktorý delí nejakú testovanú premennú o konštantu (napr. na polovicu), má zložitosť O(log n * f), kde O(f) je telo cyklu, n je testovaná hodnota
  6. ak máme spolu dva algoritmy, pri ktorých sa druhý vykoná po skončení prvého, potom majú celkovú zložitosť O(f1 + f2)
  7. rekurzívne funkcie majú často zložitosť rádovo porovnateľnú s počtom vygenerovaných výsledkov

Ukážme to na tomto príklade: pripomeňme si insert-sort z prvého ročníka:

def insert_sort(pole):
    for i in range(1, len(pole)):                   # O(n**2)
        prvok = pole[i]                      # O(1)
        j = i-1                              # O(1)
        while j >= 0 and pole[j] > prvok:           # O(n)
            pole[j+1] = pole[j]              # O(1)
            j -= 1                           # O(1)
        pole[j+1] = prvok                    # O(1)

Všetky príkazy okrem cyklov sú zložitosti O(1). Keďže premenná while-cyklu j sa znižuje o 1 a jej rozsah je priamo úmerný n, zložitosť tohto while cyklu je O(n), čo je vlastne telo for-cyklu. For-cyklus je potom n krát telo O(n), t.j. tento algoritmus je O(n**2).

Tabuľka, v ktorej sa porovnáva rýchlosť

Teraz, keď už pre naše algoritmy vieme zistiť ich časovú zložitosť, lepšie si budeme vedieť predstaviť časové obmedzenia, ktoré prichádzajú s rôzne zložitými algoritmami. Predpokladajme, že máme k dispozícii počítač, ktorý zvláda napr. 5000000 elementárnych operácií za sekundu (súčasné počítače sú výrazne rýchlejšie). Zaujíma nás, aký veľký problém by sme vedeli vyriešiť za nejaký konkrétny čas. Napr. z tabuľky nižšie je vidieť, že za jednu sekundu algoritmus zložitosti O(n log n) zvládne rozsah 280000, ale pre zložitosť O(n**3) už len rozsah 170. Podobne z tejto tabuľky môžeme vidieť, že ak nejaké pomalé triedenie (napr. bubble-sort) 17000-prvkové pole triedilo minútu, 660000-prvkové pole sa bude triediť celý deň.

                   n     nlogn      n**2      n**3      2**n
------------------------------------------------------------
mili            5000       550        71        17        12
sek          5000000    280000      2200       170        22
min        300000000  13000000     17000       670        28
hod                ∞ 620000000    130000      2600        34
den                ∞         ∞    660000      7600        39
mesiac             ∞         ∞   2300000     17000        42
rok                ∞         ∞  13000000     54000        47
1000               ∞         ∞ 400000000    540000        57

Môže nám to potvrdiť aj takýto spôsob výpočtu:

Predpokladajme, že nejaký náš program bežal pre vstup veľkosti napr. n=17000 6 sekúnd. Ak vieme, že jeho zložitosť je O(n**2), mohli by sme dosť presne odhadnúť, ako dlho bude bežať dvojnásobne väčší vstup:

  • teda f(17000) = 6 sekúnd
  • potrebujeme zistiť f(2*17000), pričom vieme, že f() je kvadratická funkcia
  • preto f(2*17000) = 4 * f(17000) = 24 sekúnd

Porozmýšľajte, ako by sa zmenil výsledok, keby bol náš program inej zložitosti, napr. O(1), O(n), O(n log n).

Príklad

Pre ilustráciu vyriešime jeden príklad z testu, ktorý bol pred tromi rokmi.

  • Pre všetky nasledujúce funkcie odhadnite časovú zložitosť: ku každej pripíšte jedno z písmen AF.

    def fun1(n):
        x = 0
        for i in range(n):
            x += 1
        return x
    
    def fun2(n):
        x = 0
        for i in range(n):
            for j in range(i):
                x += 1
        return x
    
    def fun3(n):
        if n == 0: return 1
        x = 0
        for i in range(n):
            x += fun3(n-1)
        return x
    
    def fun4(n):
        if n == 0: return 0
        return fun4(n//2) + fun1(n) + fun4(n//2)
    
    def fun5(n):
        x, i = 0, n
        while i > 0:
            x += fun1(i)
            i //= 2
        return x
    
    def fun6(n):
        if n == 0: return 1
        return fun6(n-1) + fun6(n-1)
    
    def fun7(n):
        if n == 1: return 0
        return 1 + fun7(n//2)
    

Riešenie

  • fun1 - for-cyklus n-krát telo, ktoré je O(1)
    • ==> O(n)

  • fun2 - vnútorný for-cyklus je O(n), vonkajší krát n
    • ==> O(n**2)

  • fun3 - komplikované počítanie n!
    • ==> O(n!)

  • fun4 - log n vnorení, súčet všetkých fun1(...) v každej úrovni vnorenia je maximálne n
    • ==> O(n log n)

  • fun5 - v cykle je postupné volanie fun1(n), fun1(n//2), fun1(n//4), fun1(n//8), … fun1(1) - každé z nich je O(n), O(n//2), O(n//4), O(n//8), … O(1), keď to sčítame tak je to maximálne O(2*n)
    • ==> O(n)

  • fun6 - ak by sme nakreslili strom volaní (z fun6(n) dve volania fun6(n-1), z každého z nich sú dve volania fun6(n-2), atď. až na koniec by bolo 2**n volaní fun6(0)) - dostávame úplný binárny strom výšky n s 2**n listami
    • ==> O(2**n)

  • fun7 - je to zamaskovaný while n > 1: n //= 2; ...
    • ==> O(log n)



Cvičenia

L.I.S.T.

  1. Zistite, akú časovú zložitosť má tento algoritmus triedenia:

    • bubble sort:

      def bubble_sort(p):
          b = True
          while b:
              b = False
              for i in range(len(p) - 1):
                  if p[i] > p[i + 1]:
                      p[i], p[i + 1] = p[i + 1], p[i]
                      b = True
      
  2. Nasledovný program využíva bublinkové triedenie z predchádzajúcej úlohy. Aká je jeho časová zložitosť?

    • v premennej p je nejaký pythonovský zoznam (napr. pole čísel):

      for i in range(len(p)):
          bubble_sort(p):
      
  3. Zistite časovú zložitosť týchto dvoch funkcií.

    • hoci sa líšia len v jednom znaku, majú veľmi rôznu zložitosť:

      def test1(n):
          i, j = 1, 0
          while i < n:
              j += i
              i += 1
          return j
      
      def test2(n):
          i, j = 1, 0
          while i < n:
              j += i
              i += i
          return j
      
  4. Odmerajte čas behu oboch algoritmov z (3). Použite time.time() a postupne merajte pre n: 10000, 20000, 40000, 80000, 160000, …, 5120000. Asi bude vhodné pri meraní každé volanie vykonať viackrát, napr. test1 zavolajte 100 krát a test2 10000 krát. Vypisované časy meraní by mali potvrdiť váš odhad zložitosti týchto funkcií.

  1. Odmerajte čas štandardnej funkcie sorted() pre rôzne veľké vstupy (napr. 10000, 20000, 30000, 40000, …). Ak predpokladáme, že zložitosť tejto funkcie je O(n log n), odmerané časy by to mali nejako preukázať. Použite náhodne vygenerované polia.

  1. Zistite, akú časovú zložitosť majú tieto dva algoritmy.

    • kde p je napr. nejaké pole čísel:

      def test3(p):
          i = 1
          while i < len(p):
              sorted(p)
              i += i
          return p
      
      def test4(p):
          i, n = 1, len(p)
          while i < n:
              if 2 * i >= n:
                  sorted(p)
              i += i
          return p
      

    Svoj predpoklad o časovej zložitosti prekontrolujte s rôzne veľkými náhodnými poliami.

  1. Nasledovný program vytvorí a vypíše zadaný zoznam čísel. Zistite jeho časovú zložitosť.

    • pomocou spájaného zoznamu:

      class Vrchol:
          def __init__(self, data, next=None):
              self.data, self.next = data, next
      
      def vyrob(p):
          zoz = None
          for i in p:
              if zoz is None:
                  zoz = Vrchol(i)
              else:
                  posledny = zoz
                  while posledny.next is not None:
                      posledny = posledny.next
                  posledny.next = Vrchol(i)
          return zoz
      
      def to_str(zoznam):
          res = ''
          while zoznam is not None:
              res += str(zoznam.data) + ' -> '
              zoznam = zoznam.next
          return res + 'None'
      
    • môžeme otestovať, napr. takto:

      print(to_str(vyrob(range(100))))
      

    Zistite časovú zložitosť programu to_str(vyrob(pole)) pre dané pole veľkosti n. Odmerajte čas behu pre nejaké rôzne veľké polia (napr. s počtami prvkov 10000, 20000, 40000)

  1. Opravte funkciu vyrob() z úlohy (7) tak, aby sa zásadne vylepšila zložitosť. Otestujte podobne, ako v predchádzajúcom príklade.

  1. Zistite, aká je zložitosť týchto algoritmov:

    • zisťuje akýsi súčet:

      i, j = 1, 1
      sum = 0
      while i < n:
          sum += i * j
          i = 10 * i
          j = (j + 1) % 10
      print(sum)
      
    • rekurzívny výpočet:

      def f(n):
          if n <= 1:
              return 1
          return f(n // 2) + f(n // 2)
      
    • rekurzívny výpočet - to isté ako predchádzajúci príklad, ale máličko inak:

      def f(n):
          if n <= 1:
              return 1
          return 2 * f(n // 2)
      
    • ešte jeden cyklus:

      f = 1
      while 2 * f <= n:
          f *= 2
      print(f)
      
    • rozklad čísla na prvočinitele:

      def rozklad(n):
          i = 2
          while n > 1:
              if n % i == 0:
                  n = n // i
              else:
                  i += 1
      
  2. Príklad zo záverečného testu z minulého roku. Pre niektoré z funkcií možno zatiaľ nebudete vedieť vypočítať ich zložitosť.

    • Zistiť zložitosť funkcií:

      def f1(pole1, pole2):
          if len(pole2) == 0:
              return 0
          if len(pole2) == 1:
              return int(pole2[0] in pole1)
          stred = len(pole2) // 2
          return f1(pole1, pole2[:stred]) + f1(pole1, pole2[stred:])
      
      def f2(n):
          if n == 0:
              return 1
          return n * f2(n - 1)
      
      def f3(pole):
          i = len(pole)
          while i > 0:
              for j in range(i):
                  for k in range(j, 10**5):
                      pole[j] += 1
              i -= 2
      
      def f4(n, mem={}):
          if n in mem:
              return mem[n]
          if n < 2:
              res = n
          else:
              res = f4(n-1) + f4(n-2)
          mem[n] = res
          return res
      
      def f5(pole):
          return len(pole) == len(set(pole))
      
© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.