Mester Tétel
Ennek a posztnak a témája a MergeSort algoritmus időigényének meghatározása lesz, melyet hard és easy fokozaton is meg fogunk nézni. Utóbbiban megtudjuk, mi is a címben említett Mester Tétel.
cikk
cikk
Minimum Stack
A gyakorlaton láttuk, hogyan lehet egy minimum lekérdezését támogató vermet megalkotni. Ez egy olyan megoldás volt, ahol plusz $O(n)$ tárat használtunk fel. A továbbiakban megnézzük, hogyan lehet egy teljes plusz verem helyett egyetlen változóval, azaz plusz konstans tárral ugyanezt a logikát megvalósítani.
Lineáris rekurzió
A feladat a következő: Adjuk meg a Fibonacci-sorozat $N.$ elemét $mod~P$, ahol $N\sim 10^9$ és $P\sim 10^6$ prím.
Ha ezt for ciklussal akarnánk megkapni, az $O(N)$ idő, ami sok. Ha $10^9$-dik Fibonacci számot ugyanennyi milliszekundum alatt tudnánk kiszámolni, még az is $11$ napig tartana, ha ugyanennyi másodperc alatt, akkor pedig kb $31$ évig. Ennyit azért nem szeretnénk várni!
Fast Fourier transzformáció
Hol volt, hol nem volt, létezett egy Fourier transzformáció, amit az egyetem számos kurzusán megkíséreltek megtanítani nekem, de én mégsem értettem meg. Felbuzdulva azon, hogy a kedvenc előadóm egy két órás előadást tartott erről az egészen *magic* számba ment dologról, úgy gondoltam, hosszú wikipedia és tankönyv olvasgatás helyett, amiben több a képlet és a matek, mint amit képes egy infós szem felparsolni, végignéztem az előadást. És megtörtént a csoda! Hát ez egy hihetetlenül egyszerű cucc!
Fractional Cascading
A probléma a következő: Adott $k$ db rendezett lista $(L_1, L_2, \ldots, L_k)$, mindegyik hossza $n$ és mindben meg akarjuk talalni az $x$-et vagy ha nincs benne, annak rákövetkezőjét.