Big O

Question 1

Co je Big O (+jak změřit trvání algoritmu)?

Answer 1

Big O asymptotic analysis. Big O mi říká, jak dobře je kód napsaný z pohledu škálovatelnosti (jak dlouho to trvá, než algoritmus proběhne v ohledu na počet inputu). Měření času pomoci performance.now() - let t0 na začátku a t1 na konci, time je t1-t0.

Question 2

Vysvětli O(n) - typicky příklad, jak to je time?

Answer 2

O(n) - typicky u for loop, jak zvyšuju počet elementu (napr. Počet položek v loopovanym array), zvyšuje se lineárně i počet operaci. Big O záleží na počtu n (počet elements/inputs)

Linear time

Question 3

Vysvětli O(1) a příklad, Jakej je to time?

Answer 3

Napr. Když hledám jednu konkrétní položku v array podle indexu - zabere to vždy konstantní čas bez ohledu na počet elementu. O(3) - hledá 3 položky.

Konstant time

Question 4

Vyjmenuj čtyři pravidla pro počítání Big O

Answer 4

1. Worst case
2. Remove constants
3. Different terms for inputs
4. Drop Non Dominants

Question 5

Rule 1 - worst case - vysvětli

Answer 5

Vždycky bych měl myslet na worst case scenario - mám array o 10 položkách, muže být na kterékoli, musím počítat s tím, že i na posledni -> pokud loopuju přes array, bude to O(n), kde n je počet položek.

Tip bokem -> můžeš u loop použit break a skončí to po najiti konkrétní položky (pořad muže být až na posledni pozici)

Question 6

Rule 2 - remove constants - vysvětli

Answer 6

Napr. O (3 +2n+n/3) je ve výsledku O(n). U Big O a škálovatelnosti přemýšlím o vysokých počtech inputu. Pokud mám array o milion položkách, jsou konstanty zanedbatelný (insignificant). O(2n) je more steep than 0(n) ale je to pořád z hlediska Big O linear time.

Question 7

Rule 3 - Different terms for input - vysvětli

Answer 7

Když mas funkci s jednim parametrem a dvě for loops s tímto parametrem -> O(2n) cili O(n). Když má funkce dva parametry a mám dvě for loops a každá používá jinej O( a + b) - protože mám dva různý parametry, každej muže být jinak velkej

Question 8

Rule 4 - Drop Non Dominants

Answer 8

V úvahu beres jen tu dominantnejsi (pomalejší, min skalovatelnou) variantu. O( n^2 + 3n + 100 + 2/n) je O(n^2). Teoreticky kdyby bylo n 5, pak je dominantní hodnota 100, ale u Big O nás zajímá škálovatelnost a velký čísla, pokud je n 1000, bude to na druhou milion a konstanta 100 je najednou insignificant

Question 9

O(n^2) vysvětli

Answer 9

Loops který jsou nested- místo sčítání nasobim. Quadratic time

Question 10

Data structures + algoritmy = programy

Answer 10

Dat structures - ways to Store data

Algoritmy - functions;ways tu use data structures to write our programs

Question 11

O(n!) - vysvětli, Jakej time

Answer 11

“Oh no”, když píšeš kód takhle, něco děláš špatně :) je to faktoriál time. Je to nejhorší, steepest, most expensive oné. Nedal příklad funkce. For loop pro každej element.

Question 12

3 pilíře pro dobrej kód ?

Answer 12

Readable
Memory - space complexity
Speed - time complexity

Většina řešení je trade of mezi space and time complexity

Question 13

Space complexity - co vytváří space komplexity, příklad O(1) a O(n)

Answer 13

Vytváří - adding variables, data structures, function calls, allocations.

Ve for loop mám jenom let i=0, space komplexity 1, když loopoju Db a přidávám položky do array On