Složitosti

Teorie Složitosti

​Igor Vujovič

Poll

Vyberte Váš postoj k tvrzení: "Vím co je to algoritmus, bubble sort a taky vím jak funguje paměť."

• Absolutně nemám tušení o čem je řeč

• Úplně to nefeeluju, ale někdy jsem to asi slyšel

• Spíš jo.

• Je to křišťálově jasné.

Složitost algoritmů

• Algoritmy mají různou složitost

• Existuje potřeba porovnat více algoritmů, které řeší stejný problém

• Rozlišujeme dvě přirozené míry:

1. Doba výpočtu (Časová složitost)

2. Velikost využívané paměti (Paměťová složitost)
   
   
   

Asymptotická složitost

Co to vlastně je?

• Skutečná složitost závisí na implementaci a zařízení

• Prakticky: "Jak se to chová pro velké instance?"

• Vyjádřujeme jako Řád růstu funkce (zanedbáme nižší řády)

• Asymptoticky se to blíží k této hodnotě

Každá algorismus má neklesající funkci, zvanou asymptotická (časová) složitost​

Čím pomaleji tato funkce roste, tím je algoritmus rychlejší

​Rychlost

Multiple Select

Dvě veličiny které rozlišujeme u asymptotické složitosti algorimů jsou:
(VYBERTE VŠECHNY SPRÁVNÉ ODPOVĚDI)

• Implementace konkrétního jazyka

• Časová složitost

• Paměťová složitost

• Vstupní data

Multiple Choice

Rychlejší algoritmus (s nižší časovou složitostí) je reprezentovaný funkcí:

• y = 2^x - 1

• y = log2(x)+1

Hledání 363 vs. 993 ==

​Rychlost = log2(x)
Fofrózní

Binární

Hledání 363 vs. 993 ???

​Rychlost = x
Pomalé

Lineární

Hledání v seřazeném poli

O - Landauova notace

Řešíme rychlost seřazení v strukturách a seznamech s různou kondicí (náhodně, reverzně, skoro seřazeně, opakující se hodnoty)

Řadící algoritmy

Řešíme přístupy k jednotlivým prvkům v různých scénářích (přístup k prvním/poslednímu/náhodnému prvku, aj.)

​Datové struktury

Asymptotická složitost

Home

Open in new tab

Copy link

Home

Open in new tab

Copy link

Multiple Choice

Přístup k náhodnému prvku v poli (Array) je

• O(log(n))

• O(1)

• O(n)

• O(n^2)

Multiple Choice

Přístup k nejMENŠÍmu elementu haldy (Max Heap) je:

• O(log(n))

• O(n^2)

• O(1)

• O(n)

Multiple Choice

Přístup k největšímu elementu haldy (Max Heap) je:

• O(n)

• O(1)

• O(log(n))

• O(n^2)

Multiple Choice

Bubble i insert sort mají rychlost:

• O(n^2)

• O(log(n))

• O(n*log(n))

• O(n)

Multiple Choice

Qsort, Heapsort i Mergesort mají v přůměrném scénáři rychlost:

• O(log(n))

• O(n log(n))

• O(n)

• O(n^2)

• O(1)

Problém Newyorkského Prodavače

P a NP - Třídy složitosti

Heuristické přístupy a Větvení
"některých krocích může volit z několika možností dalších kroků"

Problém splnitelnosti, Problém batohu, Traveling sales man...

Nedeterministicky Polynomiální

Problémy řešitelné pomocí deterministického Turingova stroje
Největší společný dělitel

​P - řešení v polynomiálním čase

​Vztah tříd P a NP je dosud nevyřešen!

Děkuji za pozornost

Open Ended

Secret Level: Jakou časovou náročnost má v nejhorším scénáři BOGO sort?