• Lekce 5
  • Úlohy
    • Odmocnina
  • Co jsme dnes probrali
    • Seznamy
    • Analýza časové složitosti
    • Binární vyhledávání

Lekce 5

Úlohy

Odmocnina

Spočítejte druhou odmocninu. Program na vstupu očekává celé číslo. Pokud je jeho odmocnina také celé číslo, vypíše ji. Jinak nevypíše nic. Nesmíte použít funkci math.sqrt, operátor ** a jiné.

Jde hlavně o nápad. Nejlepší možné řešení zvládne najít odmocninu ke $2^n$ na $n$ kroků. Až budete mít kód napsaný, proveďte jednoduchou analýzu časové složitosti. Jde mi o to, abyste si byli schopni uvědomit, jak dlouho program běží. Kód opatřete příslušnými komentáři.

Co jsme dnes probrali

Seznamy

• Neboli pole
• Dosud jsme se setkali s proměnnými typu číslo, řetězec, atd.
• My bychom ale chtěli používat i seznamy hodnot
  • např. seznam jmen lidí ve třídě, čísla pro výpočet aritmetického průměru
• V Pythonu seznamy hodnot píšeme do hranatých závorek [ a ]
• Příklady
  • Seznam pěti čísel

    1
    cisla = [2, 5, 3, 7, 8]
    

  • Seznam tří jmen (řetězců)

    1
    jmena = ["marek", "petr", "david"]
    

  • Seznam hodnot různých typů

    1
    hodnoty = [8, "jablko", None, 2.5, True]
    

• Můžeme se koukat na hodnoty na tzv. indexech
  • Tedy pozice v seznamu
  • V Pythonu (a ve většině programovacích jazycích) indexujeme od nuly
  • Proč od nuly?
  • Kdybychom chtěli v předchozím příkladu vypsat jméno petr, napsali bychom

    1
    jmena = ["marek", "petr", "david"]
    2
    print(jmena[1])
    3
    # Vypíše "petr"
    

  • Co se stane, když se zkusíme podívat na prvek v poli, který leží na neexistujícím indexu? Vyzkoušejte si to
• Do seznamu se přidává pomocí funkce append(x)
  • Volá se přímo na poli; máme-li tedy pole p, potom číslo 5 do něj můžeme přidat pomocí p.append(5)
  • Funkce append přidává na konec seznamu
  • Jakou má funkce append časovou složitost?
• Seznam můžeme třídit pomocí funkce sort
  • Funkci sort voláme přímo na poli, mění staré pole
  • Alternativa je zavolat funkci sorted, které předáme argumentem pole, které chceme setřídit
    • Funkce sort vrátí nové setříděné pole
  • Jak funguje třídění? Jak se porovnávají řetězce?
• Seznamem můžeme iterovat pomocí for-cyklu

  1
  jmena = ["matous", "marek", "lukas", "jan"]
  2
  for jmeno in jmena:
  3
    print(jmeno)
  4
  # Vypíše:
  5
  # matous
  6
  # marek
  7
  # lukas
  8
  # jan
  

Analýza časové složitosti

• Začali jsme v programech používat cykly, což může zapříčinit to, že program bude moci běžet dlouho
• Snažíme se tedy, aby náš program běžel co nejkratší dobu
• Koukněte se do této složky
  • Najdete tam tři programy, které počítají to stejné (druhé mocniny celých čísel do nějakého čísla)
  • fast.py se zastaví, jakmile $i^2 \geq limit$, tedy po $\sqrt{limit}$ iteracích
  • ok.py sice brzy přestane vypisovat, ale běží dál a provede limit iterací
  • slow.py využívá pole, o kterých jsme si ještě nic neříkali. Toto řešení je pomalé, protože v každé iteraci pole prohledává, což trvá dlouho
• Kdykoli píšeme program, který něco počítá, tak bychom se měli zamyslet nad tím, jak dlouho poběží
• Doba běhu typicky závisí na velikosti vstupu. Tato velikost se běžně značí n.
  • V příkladové úloze to je hodnota limit
  • Pokud bychom počítali průměr čísel, byl by to jejich počet
  • Pokud bychom počítali délku řetězce, byla by to jeho délka
  • Doba běhu ovšem může záviset na více hodnotách, např. zpracování obrázku bude záviset na jeho šířce a výšce
• Nás zajímá to, jak dlouho bude program běžet v závislosti na velikosti vstupu
  • Nejvíce nás zajímá to, jak bude program běžet pro velké vstupy (říkáme tomu nejhorší případ)
• Také se snažíme zjistit, kolik operací program vykoná
• Pojďme analyzovat řešení ok.py
  • Odteď budeme proměnné limit říkat n
  • Na začátku programu...
    • ...vezmeme vstup od uživatele
    • ...převedeme ho na int
  • To jsou 2 operace, které se vykonají vždy
  • Poté máme for cyklus
    • Ten se provede nkrát
    • V něm se vždy (pro každou iteraci cyklu)
      • zvýší hodnota i o jedna
      • vypočte druhá mocnina i
      • provede se porovnání $i^2 < n$
  • To je dalších $3n$ operací
  • Ale tady nekončíme. Kolikrát se provede kód na řádce 4?
    • Provede se $\sqrt{n}$ krát
      • Proč zrovna $\sqrt{n}$ krát
      • Podmínka v ifu je takováto: $i^2 < n$
      • Upravíme na $i < \sqrt{n}$
      • Vidíme, že po $\sqrt{n}$ iteracích začne být $i^2$ větší, než $n$
    • Co se v tomto ifu stane?
      • spočte se $i^2$
      • vytiskne se hodnota $i^2$
    • Celkem tedy $2\sqrt{n}$ operací
  • Sečteno podtrženo to je $3n + 2\sqrt{n} + 2$ operací
  • V teoretické informatice řekneme, že doba běhu našeho algoritmu leží ve třídě $\mathcal{O}(n)$
    • Slovo třída znamená skupina (množina) funkcí. V tomto případě skupina $\mathcal{O}(n)$ značí všechny funkce, které rostou nejvýše tak rychle, jako nějaká lineární funkce.
    • Naše funkce do ní rozhodně patří
    • Například naše funkce $3n + 2\sqrt{n} + 2$ roste pomaleji, než $4n$
    • U asymptotické notace můžeme krátit konstanty a zbavovat se pomaleji rostoucí členů
• Více si o složitosti můžete přečíst tady

Analýza fast.py

• Na začátku se provedou dvě operace
  • Načtení vstupu
  • Inicializace proměnné i
• Ve while cyklu se provedou tři operace
  • Umocní se i na druhou
  • Vytiskne se
  • Inkrementuje se proměnná
• Samotný while cyklus se provede nanejvýš $\sqrt{limit}$krát
• Celkově tedy kód provede $3\sqrt{limit} + 2$ operací
  • Náš algoritmus je tedy v $\mathcal{O}(\sqrt{limit})$
  • Dokonce leží i v $\Theta(\sqrt{limit})$

Analýza slow.py

• Na začátku se provedou dvě operace
  • Načtení vstupu
  • Inicializace pole integers
• Poté se provede $limit$ iterací prvního cyklu
  • Každý krok cyklu se provede jedna operace, a to vložení do seznamu
  • Funkce append má amortizovanou časovou složitost $\mathcal{O}(1)$
    • To, co je amortizovaná časová složitost, se dozvíte ve druhém semestru na vysoké škole
• Druhý cyklus také provede $limit$ iterací
  • Každý krok cyklu se provedou dvě operace
    • Operace in zjistí, jestli je j**(1/2) v poli integers
      • Tato operace trvá $\mathcal{O}(limit)$
• Celkový čas druhého cyklu je tedy $\mathcal{O}(limit^2)$
• Celkem tedy náš algoritmus potvrá v nejhorším případě $\mathcal{O}(limit^2)$

Binární vyhledávání

• Když máme seřazené pole, můžeme v něm hledat rychleji než prohledáváním od začátku (v lineárním čase)
• Tomuto se říká binární vyhledávání, protože v každém kroku hledání zmenšíme počet prvků, ve kterých hledýme, na polovinu
  • Můžeme to udělat, protože je pole setříděné

1
seno = [1, 2, 4, 6, 8, 9, 11, 16, 26, 30]
2
jehla = 10
3

4
delka = len(seno)
5

6
# Pouzijeme tzv. metodu dvou jezdcu. Jeden je na zacatku, druhy na konci pole.
7
# Stred je prumer techto dvou jezdcu.
8
levy = 0
9
pravy = delka - 1
10
stred = (pravy - levy) // 2
11

12
# Vsimneme si, ze behem behu algoritmu se levy vzdy posouva doprava a pravy
13
# doleva. Jakmile se prekryji, muzeme smycku ukoncit.
14
while pravy > levy:
15
    # Pri prohledavani muzou nastat tri pripady:
16

17
    # Jehla je ve stredu, nasli jsme ji.
18
    if jehla == seno[stred]:
19
        print("cislo je v seznamu!")
20

21
        # Ukoncime cyklus, protoze dal hledat nemusime.
22
        break
23
    elif jehla < seno[stred]:
24
        # Pokud je jehla v leve polovine, pravy ukazatel nastavime na jednu
25
        # pozici nalevo do stredu (nalevo, protoze budeme hledat v leve
26
        # polovine).
27
        pravy = stred - 1
28

29
        # Levy ukazatel zustava na sve pozici, musime ale prepociat stred.
30
        stred = (pravy + levy) // 2
31
    else:
32
        # Analogicky k predchozimu pripadu.
33
        levy = stred + 1
34

35
        stred = (pravy + levy) // 2

• Binární vyhledávání má časovou složitost $\mathcal{O}(\log n)$
  • V každém kroku zmenšíme počet prvků, ve kterých hledáme, na polovinu
  • Pokud máme $n$ prvků, tak je potřeba $\log_2 n$ kroků, abychom se dostali na 1 prvek
    • Protože $2^{\log_2 n} = n$