Bonyelm gyakjegyzet 2014, 1. gyak

re,

kicsit off voltam nyáron. Nemsokára folytatom a regexes threadet is (remélem), addig is elkezdek itt egy bonyelm gyakjegyzetet loggolni :-)

Első jóhír, hogy jótanácsot követve belőttem a MathJaxet, úgyhogy most már talán ki fognak nézni valahogy a matekos jelek is.

Első gyakorlaton (követelményismertetés után ofc) felidéztük, hogy futásidőket és tárigényeket akarunk majd összehasonlítani és számolgatni, ezeket pedig elég lesz csak nagyságrendben ismernünk, nem a pontos függvényeket. Ha $f$, $g$ függvények (mondjuk természetes számokat valós számokra képezőek, de lehet az értelmezési tartomány is a pozitív valós, vagy az értékkészlet a természetes, mindegy), akkor azt mondjuk, hogy $f=O(g)$ (ami kb. a "$g$ legalább olyan gyorsan nő, mint $f$"-nek felel meg), ha van olyan $c>0$ konstans, amire $f\leq c\cdot g(n)$ majdnem minden $n$-re (ami matekul ugyanaz, mint hogy "van olyan $N$ küszöbszám, hogy ha $n>N$, akkor már igaz).

• Például, $3n=O(\frac{n^2}{100})$, mert ha $c=100$ és $N=3$, akkor tényleg fennáll, hogy ha $n>3$, akkor $3n \leq 100\cdot\frac{n^2}{100}=n^2$ (egyszerűsítünk $n$-nel, kész).

Az $O$ (e. ordó) kapcsolatnál szigorúbb az $o$ (kisordó) kapcsolat: $f=o(g)$, ha tetszőleges $c>0$-ra $f(n)\leq c\cdot g(n)$ majdnem minden $n$-re. (Ez kb. a "$g$ gyorsabban nő, mint $f$"-nek felel meg.) Ilyenkor már nem mondani kell egy $c$-t és egy $N$-t, hanem tetszőleges $c>0$-ra mondani kell egy $N$-t, amitől kezdve igaz az összefüggés.

• Például, $3n=o(\frac{n^2}{100})$ is igaz, hiszen ha $c>0$, akkor átrendezve kapjuk, hogy ha $\frac{300}{c}\leq n$, akkor $3n\leq c\cdot\frac{n^2}{100}$.

Ezután megláttuk a $\log^2 n=o(n)$ feladatot.. hát erre input $c>0$ küszöbszámra mondani megfelelő $N$-t már nem nekünk való feladvány (megjegyzés: a $\log$ mindig kettes alapú logaritmust jelent, mi mást, a $\log^2 n$ pedig a $(\log n)^2$-nek egy átláthatóbb formája. Nem pedig pl. a $\log\log n$-nek). Szerencsére "tudjuk", hogy ha $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$, akkor $f=o(g)$. Ha pedig a limesz legalábbis kisebb, mint végtelen (tehát például 7, 0 vagy $\pi$), akkor $f=O(g)$ lesz.

Ezután már könnyű volt, mert $\lim_{n\to\infty}\frac{\log^2 n}{n}$ a L'Hopital-szabály szerint ugyanannyi, mint $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\log n}{n}$, ami megint ugyanemiatt a szabály miatt $\lim_{n\to\infty}\frac{2\cdot\ln 2\cdot\ln 2}{n}$, ami tényleg $0$, tehát $\log^2 n=o(n)$. Persze akármilyen $k>0$ konstanst is mondunk, ezek szerint $\log^k(n)=o(n)$ is igaz lesz - ez nálunk annyit tesz, hogy akár futásidőről, akár tárigényről lesz szó, a $\log^k(n)$ alakú erőforrás-igényt jobbnak fogjuk tartani, mint a lineárist. (A $\log^k(n)$ alakú függvényeket egyébként polilogaritmikus függvénynek hívjuk.) Persze ha szekvenciális algoritmusról beszélünk, annak nem lehet $o(n)$ (amit szublineárisnak is mondunk) az időigénye, hiszen ennyi lépésben nem tudja végigolvasni se az inputot. Amikor elő fognak jönni szublineáris függvények:

• tárigénynél;
• párhuzamos számítás időigényénél.

Példaképp felhoztam, hogy az ${Elérhetőség}$ probléma (input: irányított gráf, csúcsai $1$-től $n$-ig a számok, output: van-e út $1$-ből $n$-be?) az egy könnyű probléma, lineáris időigényű algoritmus van rá, pl. a mélységi keresés. Vagy a szélességi. Viszont ezek az algoritmusok mind $n$ tárat használnak (mert jelölgetik a csúcsokat). Házi jellegű feladatra kértem, hogy próbáljunk készíteni szublineáris tárigényű algoritmust, ami szintén eldönti az ${Elérhetőség}$ problémát.

Megnéztük még azt is, hogy $n^2=o(2^n)$, hiszen két L'Hopital szabály után kapjuk, hogy $\lim\frac{n^2}{2^n}=\lim\frac{2n}{\ln 2\cdot 2^n}=\lim\frac{2}{\ln 2\ln 2\cdot 2^n}=0$. Általában is igaz, hogy ha $p$ polinom, $e$ pedig exponenciális függvény, akkor $p=o(e)$, legyen akármekkora a polinom fokszáma és akármilyen pici is az $e$ alapja. Általában futásidőről ha szó lesz, akkor a polinomnak fogunk örülni, azt tekintjük hatékony algoritmusnak, ami polinom időigényű (legrosszabb esetben is), és egy problémát hatékonyan megoldhatónak akkor hívjuk, ha van rá polinom időigényű algoritmus. (Ez a Cobham-Edmonds tézis.)

Házi jelleggel megnézhetjük, hogy az exponenciális lassabban nő, mint $n!$, ami pedig lassabb, mint a $2^{n^2}$.