vahy ---- a) 1) n liche => jednu vynecham, vazim nahodne poloviny, n sude => nevynecham nic a jdu rovnou na 3) 2) vazi stejne => ta vynechana je hledana, konec, konstantni slozitost 3) vazi jinak => vynechana me nezajima, hledana je v jedne hromadce podle toho jestli je tezsi nebo lehci 4) v kazdem dalsim kroku rozpulim zbylou hromadku a zvazim poloviny kdyby mi mely vyjit necele (liche cislo/2), bud jednu odeberu jako v 1), nebo si pomuzu pridanim nektere z uz vyrazenych (vazi stejne jako ty co nehledam, takze mi to nezkazi) preferovat budu tu metodu, ktera me vyrobi vetsi x, kdyz 2^x deli n (o to vic cistych puleni za sebou budu pak mit a nebudu muset nic resit) pokud se mi nelibi reseni delitelnosti (napr. z fuvodu toho ze by mi pokazilo casovou slozitost), pouziju tu prvni metodu k ziskani sudeho n 5) po poctu kroku ~ log2(n) dospeju do situace kdy mi zbyde 1 kulicka - ta hledana ...logaritmicka casova slozitost b) 1) inicializace na sude n jako v a), ale opakuju ji, dokud nedostanu cislo, ktery bude mit sude i poloviny (tozn. je delitelne 4) 2) pokud jsem v 1) neskoncil rozdelim na 2 poloviny, po vazeni vyjde jedna tezsi, jedna lehci 3) jednu ze skupin (treba tu lehci) vezmu, rozdelim na 2 poloviny (diky inicializaci na 4 bez zbytku) 4.1) obdrzim rovnost => zahodim tuhle pulku, neznama kulicka je tezsi, dal jako posledni krok 4) v a) 4.2) obdrzim nerovnost => zahodim druhou pulku, neznama kulicka je lehci, dal jako krok 4) v a); zde jsem jedno vazeni usetril, protoze jsem zjistil i v polovine z tech lehcich je pozn. asymptoticka slozitost zde bude stejna jako v a), operacni muze mit o par jednotek navic kvuli snaze o n delitelne 4 nebo kdyz si neusetrim vazeni navic kvuli zjistovani, jestli je hledana kulicka lehci nebo tezsi c) pripad: 15 kulicek, jina je kulicka c. 6, vim, jesli je tezsi/lehci postup: 1) 15. vynecham, vazim 2) vazi jinak => mam 1..14 a protoze vim, jaka pulka me ma zajimat, mam 1..7 3) zda napr. doplnim na 1..8, vazim 4) tezsi je 5..8, vazim 5) tezsi je 5..6, vazim 6) tezsi je 6, konec pocet vazni: IIII = 4 ~= log2(15) d) 1) jednu kulicku (treba prvni) zvolim za referencni 2) vsechny s ni porovnam 3) separuju stejne a nestejne (nestejne budou bud vsechny tezsi nebo vsechny lehci) 4) nakonec pridam referencni kulicku k tem, ktere vazili stejne pocet vazeni je presne n-1... linearni casova slozitost porovnani --------- v obecnem pripade se porovnavaji vsechny cifry, tozn. porovnani ma nejhure logaritmickou slozitost v nejlepsim pripade staci prvni porovnani, abychom zjistitli ze jsou cisla ruzna => nejlepsi slozitost je konstantni (1) prumerna slozitost? 1) vezmu vsechna cisla, z rozsahu 0..n, jedno referencni vyberu nahodne (treba 0, ma v zapisu same 0-bity) 2) rozdelim je do n mnozin podle toho, na kolikatem bitu se lisi oproti referencnimu cislu 3) vypocitam vazeny prumer x z poctu nutnych porovnani (index cifry, kde se budou poprvel lisit); vahami zde bude mohutnost mnozin sestavenych dle 2) necht m = ceil(log2(n)) ... pocet bitu v zapisu cisla (ceil viz C funkce z math.h) pocet vsech cisel = n = 2^m pocet cisel lisicich se na indexu 1 = 2^(m-1) pocet cisel lisicich se na indexu 2 = 2^(m-2) ... pocet cisel lisicich se na indexu m = 2^(m-m) = 2^0 = 1 pocet cisel totoznych s referenci = 1 ... zde potrebuji taky m porovnani, abych zjistil se nikde nelisi => prispevek do prumeru bude m, vaha 1 ------------------------------------------------------- celkem cisel = 2^m (pocet podmnozin mnoziny s m prvky) 1*2^(m-1) + 2*2^(m-2) ... + m*2^0 + m*1 x = --------------------------------------- = 1/2^1 + 2/2^2 + ... + m/2^m + m/2^m = 2^m = Suma[k/2^k; k=1; m] + m/2^m = 2^(-m)*(-2+2^(1+m)-m) + m/2^m = (-2+2^(1+m))/2^m = 2 - 2^(1-m) =========== ... toto je prumerna slozitost porovnani v zavislosti na poctu bitu vstupu = 2 - 2^(1-ceil(log2(n))) ~ 2 - 2^(1-log2(n)) ======================= ... toto je prumerna slozitost porovnani v zavislosti na rozsahu uvazovanych cisel a) lim[2 - 2^(1-ceil(log2(n))); n->OO] ~ lim[2 - 2^(1-log2(n)); n->OO] = 2 - lim[2^(1-n); n->OO] = 2 - 2^-OO = 2 - 0 = 2 = => na dostatecne velkem vzorku dat se bude prumerna slozitost porovnani nekonecne velkych cisel blizit konstantni slozitosti = 2 (bereme porovnani 2 binarnich cislic jako operaci s casovou slozitosti = 1) razeni retezcu -------------- casova slozitost (na pocet porovnani) pouziteho radiciho algoritmu <=> SRP casova slozitost (na pocet swapu) radiciho algoritmu <=> SRA uzitim analogickeho odvozeni z prechoziho prikladu (porovnani) zjistime slozitost porovnani radku o s znacich v experimentu pouziju retezce postavene nad mnozinou 10 znaku (cislo Pi na 1E6 mist s delkou radek s=100) asymptoticka slozitost tohoto porovnani (decimalni cisla) je 10/9, coz je ~= 1 (ani pro s je 100 nebo nekonecno se uz temer nelisi) porovnani v ramci radicich algoritmu vsak nebude porovnavat 2 uplne nahodne radky, ale bude se s obsahy stale vic a vic blizit, jak dostava podobne radky k sobe, nezbyva nez zkusit SRP pro par algoritmu (viz nize) vysledna casova slozitost razeni bude: SRP * (casova slozitost porovnani 2 retezcu o s znacich, ovsem v ramci razeni!) + SRA * (casova slozitost swapu 2 retezcu o s znacich) = |posledni faktor necht je konstanta = 3 (3 operace na swap pointeru)| = SRP * (casova slozitost porovnani 2 retezcu o s znacich) + SRA*3 pro konstantni distribuci pravdepodobnosti moznosti vstupu jsou prumerne slozitosti radicich algorimtu: algoritmus casova slozitost prumerna slozitost porovnani prumerna slozitostu presunu ------------------------------------------------------------------------------------------------------------------------------------- BubbleSort O(n^2) n^2/2 n^2/2 BubbleSort s pameti O(n^2) n^2/2 n^2/8 SelectSort O(n^2) n^2/2 n InsertSort O(n^2) n^2/4 n^2/8 InsertSort s pulenim O(n^2) n*log(n)*1 n^2/8 QuickSort O(n^2) n*log(n)*1.4 zalezi na implementaci, cca n*log(n) MergeSort O(n*log(n)) n*log(n)*1 n*log(n) HeapSort O(n*log(n)) n*log(n)*2 zalezi na implementaci, cca n*log(n) RadixSort O(n) hrozne moc krat n, a hlavne pro delsi stringy nepouzitelny, nebudu dale uvazovat BogoSort O(n*n!) n*n! n*n! casova slozitost razeni radku o s znacich pro ruzne algoritmy bude: algoritmus casova slozitost razeni radku o s znacich ------------------------------------------------------------------------------------------------------------------------------------- BubbleSort n^2/2 * SRP + 3n^2/2 BubbleSort s pameti n^2/2 * SRP + 3n^2/8 SelectSort n^2/2 * SRP + 3n InsertSort n^2/4 * SRP + 3n^2/8 InsertSort s pulenim n * SRP + 3n^2/8 QuickSort n * SRP + 3n*log(n) MergeSort n * SRP + 3n*log(n) HeapSort n * SRP + 3n*log(n) BogoSort n*n!*(SRP + 3) experiment: radky jsou kusy zapisu cisla Pi na 1E6 mist, delka radek s=100, pocet radek= 1E6/100 = 10k ziskane pocty operaci, prumerne operacni slozitosti a prumery poctu porovnanych znaku (zde cislic) na jedno porovnani radku: algoritmus pocet porovnani; slozitost pocet presunu; slozitost pocet porovnanych cislic; prumer na porovnani ------------------------------------------------------------------------------------------------------------------------------------- BubbleSort s pameti 49987860; 0.4998*n^2 24821234; 0.25*n^2 230651529; 4.61415 SelectSort 49995000; 0.4999*n^2 10000 ; n 155658278; 3.11348 InsertSort s pulenim 128970 ; 0.97*n*log(n) 24821235; 0.25*n^2 591624 ; 4.5873 QuickSort, hloupe presuny 188811 ; 1.42*n*log(n) jako Bubble 822290 ; 4.3551 MergeSort 120459 ; 0.91*n*log(n) 118412 ; 0.89*n*log(n) 534414 ; 4.4365 zaver: operacni slozitosti odpovidaji (az na presuny InsertSortu, coz bude zpusobeno specificnosti vzorku dat) prumerny pocet porovnanych znaku (cifer) na porovnany radek ma nejvetsi BubbleSort (casto porovnava data blizko sebe) naopak nejmene do hloubky pri porovnavani radku vstupuje SelectSort, ktereho od prirody rozlozeni dat moc nezajima damy na sachovnici ------------------ 1) umistim 1. damu do prvniho radku nebo sloupce (volme napr. sloupec, pro radek by to bylo analogicky) 2) v bodu 1) jsem vybral jednu z 8 moznosti (ostatni vyberu pozdeji v ramci jedne urovne rekurze), oznacim pole, ktere dama ohrozuje (muzu zacit az v dalsim sloupci) 3) umistim dalsi damu do dalsiho sloupce na jedno z poli ktere neni zatim ohrozeno, garde je symetricka relace, takze nebude ohrozena zadna z jiz umistenych dam na sachovnici 4) v bodu 3) jsem vybral jednu z vice moznosti (ostatni vyberu pozdeji v ramci jedne urovne rekurze), oznacim pole, ktere dama ohrozuje (muzu zacit az v dalsim sloupci) 5) opakuji od bodu 3) dokud neumistim vsechny damy, tuto situaci si zapamatuji; po navratu z podprocedury zkousim na aktualni urovni rekurze i ostatni moznosti vyberu neohrozenych poli 6) po skonceni procedury zacinajici v bode 1) si pamatuji vsechny mozne rozmisteni dam odpovidajici zadanym pozadavkum a) slozitost algoritmu je O(n!), protoze na zacatku mam 8 moznosti jak umistit damu a kazde dalsi umisteni mi zakryje 1-3 nove pole a 1-2 stare se dostanou umistenych dam s tim, ze ta posloupnost je monotonni => ma to faktorialovou obalku b) operacni slozitost umistovani dam je fatorialova a do casove pribyde jeste kvadraticka slozitost zjistovani ohrozovanych poli (sachovnice je n*n), takze O(n^2*n!), horsi nez BogoSort... c) 294.226.732.800.000 casovych jednotek by se v meritku operacni rychlosti dnesnich CPU v relaci k lidskemu zivotu jeste nechalo vyresit, ale nestastnik, ktery by cekal na dokonceni vypoctu by tento cas urcite nenazyval "rozumnym"