12 riešení:
Jazyk | Počet | Čas | Kód | Veľkosť | poznámka |
---|---|---|---|---|---|
C++ |
1 | 1,19 s | 38 riadkov | 727 B | vector<vector<long long>> |
Java |
11 | 0,51 - 5,90 s | 31 - 97 riadkov | 916 - 3.195 B | predpočítanie hodnôt, priebežné modulovanie, BigInteger , BufferedReader / Scanner , try-catch namiesto porovnávania |
https://ics.upjs.sk/~rkb/asu1/hladaj.py
Ktoré funguje a ktoré nie (dokážte správnosť a vypočítajte zložitosť, resp. nájdite kontrapríklad)
Ako funguje dynamické pole?
Java
je implementované v ArrayList
-e, podľa dokumentácie majú operácie nasledovnú zložitosť:C++
je implementované vo vector
-e, zložitosť podľa dokumentácie:
V jazyku Python
je implementové v zozname list, []
.
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ť.
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$.
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
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.
Definujeme 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)$, definujeme 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.
napr.:
0000
0001
0010
0011
0100
0101 ... 1+4 = 5
0110
0111
1000
- 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)
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á.
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$.
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$