Úloha SuMax¶

41 riešení:

Jazyk	Počet	Čas	Veľkosť
`C++`	4	0,6-1,56 s	1.830-4.709 B
`Python`	10	6,56-22,57 s	1.574-3.195 B
`Java`	27	0,65-6,96 s	2.517-5.392 B

suma môže presiahnuť 32 bitový int
občas chyba +-1 v indexovaní
2 intervalové stromy alebo 2 hodnoty vo vrchole

Dynamické pole¶

Ako funguje dynamické pole?

V jazyku Java je implementované v ArrayList-e, podľa dokumentácie majú operácie nasledovnú zložitosť:

V jazyku C++ je implementované vo vector-e, zložitosť podľa dokumentácie:

V jazyku Python je implementové v zozname list, [].

https://wiki.python.org/moin/TimeComplexity

Podľa wikipédie sa pole v jednotlivých implementáciach zväčšuje rôzne:

Napr. ak začíname s kapacitou 100 prvkov, tak postupné pridávanie prvkov má zložitosť (pri faktore 2):

$$1+1+..+1+(200+101)+1+1+...+1+(400+201)+1+1+...$$

Zložitosť jednej operácie pridania je teda $O(n)$.

Pridanie $n$ prvkov má teda zložitosť $O(n^2)$.

Toto je len hrubý horný odhad, tesný odhad pre pridanie $n$ prvkov je $\Theta(n)$. Pridanie každého prvku má zložitosť $O(1)$ a v prípade naplnenia kapacity ešte navyše nová veľkosť poľa, teda v uvedenom príklade $200+400+800+1600+... = O(n)$.

Bola definovaná amortizovaná zložitosť, určujúca "priemernú časovú zložitosť". Na výpočet zložitosti celého programu teda môžeme počítať počet operácií $\times$ amortizovaná zložitosť.

Amortizovaná zložitosť¶

Technika umožňujúca presnejšie určenie zložitosti. Uvažujme výpočet, v ktorom sa postupne vykonajú inštrukcie $I_1, I_2, \dots, I_n$.

klasický prístup: Analyzujeme zložitosť každej operácie. Výsledná zložitosť je súčtom zložitostí jednotlivých operácií.
technika amortizácie: Analyzujeme postupnosť ako celok.

dynamické pole

zásobník s MULTIPOP výberom

  PUSH - vložiť jeden prvok na vrch
  POP - vybrať jeden prvok
  MULTIPOP - vybrať k prvkov

binárne počítadlo ($k$-bitové)

  pole k bitov ... {0, 1}^k

  INCR - zvýšiť počítadlo o jedna

Metódy¶

zoskupení

Operácie rozdelíme do skupín a analyzujeme zložitosť celej skupiny operácií súčasne.

účtov

Každej operácii priradíme kredit (číslo), ktoré môže byť rôzne od jej skutočnej ceny (zložitosti). Pri realizácii operácie zaplatíme jej cenu kreditmi podľa nasledovných pravidiel:

– ak cena operácie ≤ kredit operácie, tak za operáciu zaplatíme toľko kreditov, aká je jej cena, a zvyšné kredity uložíme na účet

– ak cena operácie > kredit operácie, tak kredity potrebné na zaplatenie operácie vezmeme z účtu.

Počiatočný stav účtu je 0 kreditov.

Ak počas celého výpočtu je počet kreditov na účte nezáporný, tak súčet kreditov vykonaných operácií je ≥ cena vykonaných operácií.

Kredity priradíme objektom štruktúry údajov, nad ktorou sa operácie realizujú. Cena operácie sa zaplatí kreditmi objektov, s ktorými operácia manipuluje.

Amortizovaná cena operácie = počet kreditov priradených operácii.

potenciálových funkcií

Operácie sa realizujú nad štruktúrou údajov. Potenciálová funkcia $\Phi$ priradí každej hodnote (obsahu) štruktúry údajov číslo.

Uvažujme postupnosť $n$ operácií, nech skutočná cena $i$-tej operácie v tejto postupnosti je $c_i$ .

Označme $D_0$ počiatocnú hodnotu štruktúry údajov a $D_i$ jej hodnotu po vykonaní $i$-tej operácie.

Deﬁnujeme amortizovanú cenu $i$-tej operácie, $\hat{c}_i = c_i+\Phi(D_i)-\Phi(D_{i-1})$.

Súčet amortizovaných cien operácií je $\sum\limits^{n}_{i=1} \hat{c}_i = \sum\limits^{n}_{i=1} \left(c_i+\Phi(D_i)-\Phi(D_{i-1})\right) = \sum\limits^{n}_{i=1} c_i + \Phi(D_n)-\Phi(D_0)$

Za predpokladu $\Phi(D_n) \ge \Phi(D_0)$ platí $\sum\limits^{n}_{i=1} \hat{c}_i \ge \sum\limits^n_{i=1} c_i$ t.j. súčet amortizovaných cien operácií je horným odhadom pre zložitosť celej postupnosti operácií.

Aby sme zabezpečili platnosť podmienky $\Phi(D_n) \ge \Phi(D_0)$, deﬁnujeme potenciálovú funkciu tak, aby pre každú hodnotu $D$ štruktúry údajov platilo, že jej potenciál $\Phi(D)$ je aspoň taký veľký, ako potenciál počiatočnej hodnoty $\Phi(D_0)$ štruktúry údajov.

binárne počítadlo ($k$-bitové)¶

napr.:

    0000
    0001
    0010
    0011
    0100
    0101 ... 1+4 = 5
    0110
    0111
    1000

zoskupíme po bitoch/stĺpcoch:

    - posledný bit sa mení stále ... O(n)
    - predposledný bit sa mení po každom druhom pripočítaní ... O(n/2)
    - tretí bit sprava sa mení po 4 pripočítaniach ... O(n/4)

$$n+\frac{n}{2}+\frac{n}{4}+...= 2n $$

Celková zložitosť $n$ operácií je $O(2n)$, a teda amortizovaná zložitosť je $O\left(\frac{2n}{n}\right) = O(2) = O(1) $, t.j. konštantná.

účty

operácia	cena	kredit
nastavenie bitu na 0	1	0
nastavenie bitu na 1	1	2

Počas celého výpočtu platí invariant, ak je bit nastavený na 1, tak má na svojom účte 1 kredit.

Počas operácie Inc sa mení hodnota bitu na 1 práve raz. Preto amortizovaná cena operácie Inc je 2 a cena zložitosti postupnosti $n$ operácií Inc je $2n$.

potenciálová funkcia

Zvoľme potenciálovú funciu $\Phi$ ako počet jedničiek v počítadle, označme $b_i$ počet jedničiek v počítadle po vykonaní $i$ operácií.

Zjavne $D_0 = 0$. Cenu $i$-tej operácie označme $c_i = 1+t_i$, kde $t_i$ počet bitov preklopených z 1 na 0.

$\hat{c}_i = c_i+\Phi(D_i)-\Phi(d_{i-1}) =(1+t_i)+b_i-b_{i-1} = (1+t_i) + (b_{i-1}-t_i+1) - b_{i-1} = 2$

$\sum\limits^n_{i=1} c_i \le \sum\limits^{n}_{i=1} \hat{c}_i = \sum\limits^{n}_{i=1} 2 = 2n$

https://is.muni.cz/elportal/estud/fi/js06/ib108/Navrh_algoritmu_II.pdf

Binárny Vyhľadávací Strom `Binary Search Tree`¶

rodič má najviac dvoch potomkov - ľavý podstrom sú hodnoty menšie, pravý väčšie
nájdenie prvku v BVS má zložitosť výšku stromu

https://algs4.cs.princeton.edu/32bst/

Samovyvažovacie vyhľadávacie stromy `Balanced Search Tree`¶

rozdiel výšok podstromov nemôže byť viac ako 1 ... AVL stromy [1962 Georgy Adelson-Velsky, Evgenii Landis]

https://en.wikipedia.org/wiki/AVL_tree

https://ksp.mff.cuni.cz/kucharky/vyhledavaci-stromy/

2-3 stromy [1970 John Hopcroft], červeno-čierne stromy Black Red Trees [1972 Rudolf Bayer]

https://algs4.cs.princeton.edu/33balanced/

https://kubokovac.eu/gnarley-trees/23tree.html

splay stromy [1985 Daniel Dominic Sleator, Robert Endre Tarjan]

https://kubokovac.eu/gnarley-trees/Splay.html

stromohalda Treap [1989 Raimund Seidel, Cecilia R. Aragon]

http://opendatastructures.org/ods-python/7_2_Treap_Randomized_Binary.html

Zovšeobecnenia intervalového stromu:¶

K-d tree (https://en.wikipedia.org/wiki/Kdtree) [1975 Jon Louis Bentley]
Analyses of binary search trees has found that the worst case time for range search in a k-dimensional k-d tree containing n nodes is $O\left(k \cdot n^{1-\frac{1}{k}}\right)$

http://palma.strom.sk/aux/quadrant/

R-tree (https://en.wikipedia.org/wiki/R-tree) [1984 Antonin Guttman]

The R-tree can also accelerate nearest neighbor search for various distance metrics

In [ ]: