Koliko je složena analiza složenosti?

Algoritam 

Probati ću pokazati kako analiza jednostavnog algoritma može biti dosta zahtjevna. Analizirati će se algoritam koji generira slučajnu permutaciju brojeva 1 do N. Jednostavan programski kod u jeziku Python dan je u nastavku:

N = int(sys.stdin.read())
memory = set()
while(len(memory) < N):
    genNumber = random.randrange(0, N) #0 to N-1
    memory.add(genNumber)
    print(genNumber)

Pretpostavka

Pretpostavka za analizu je da struktura set radi u O(1) vremenu. Na kraju će biti dano rješenje u O(N) vremenu i algoritam koji je posve jednostavan za analizu jer se odmah iz algoritma vidi složenost.

Iz algoritma se vidi da broj koraka za zadani N nije određen. Zbog slučajne prirode koja se zbiva, teoretski ovaj program ne mora nikad završiti. Pa kako onda raditi analizu? Ideja je slična kao i kad bi radili analizu QSort-a gdje se pivot odabire slučajno. Vremenska složenost će biti očekivani (matematičko očekivanje) broj koraka za zadani N.

Nekako intuitivno se čini da će složenost algoritma u prosjeku biti eksponencijalna, što naravno nije dobro. Ali da li je to istina?
Probajte si u ovom trenutku zapisati Vašu pretpostavku koja je složenost, čisto ovako od oka, pa na kraju usporedite s rezultatom.

Izvod

Za izvod prvo nam je potreban model tj. slučajna varijabla s kojom ćemo prikazati dati proces (algoritam). Broj koraka k definirat ćemo kao broj koraka koji algoritam mora napraviti nakon što je već napravio N koraka. Razlog tome je što algoritam mora napraviti barem N koraka, pa da se ne komplicira s tim dodatnim N-om bolje je uzeti samo taj dodatak. Vidimo iz definicije problema da je najmanja vremenska složenost O(N), pa ako se i dobije da očekivani broj koraka tj. taj dodatak manji od N, ukupna vremenska složenost će biti O(N).

Do sada ništa pametno. Idemo na model. Kolika je vjerojatnost da algoritam završi u 0 dodatnih koraka: $$\frac{N!}{N^{N}}$$ Kolika je vjerojatnost za k dodatnih koraka? Ovo je već malo teži problem. Kolika je vjerojatnost za jednu permutaciju tj. da baš u tom redoslijedu program izgenerira N+k brojeva. Zbog neovisnosti vrijedi: p(1)*p(2)...p(N)...p(N+k). Ako si zamislimo generator kao bubanj s lopticama, vjerojatnost da u svakom koraku izvučemo neki broj je $$\frac{1}{N} \ tj.\ ukupno\ je\ to\ p = \frac{1}{N^{(k+N)}}$$ To je lakši dio. Teži dio je naći broj permutacija za koje igra završava baš u tom koraku k. Ono što je očito da zadnji generirani broj prije zaustavljanja algoritma je jedinstven u cijelom generiranom nizu, zato što je on jedini nedostajao. Znači na zadnje mjesto može ići jedan od N brojeva. Na preostalih N+k-1 mjesta svrstava se N-1 brojeva. Bitno je da se svaki od N-1 brojeva mora pojaviti barem jednom na intervalu od prvog generiranog do predzadnjeg generiranog broja jer postoji samo jedan broj koji je zadnji i taj je jedinstven. Npr. za N = 5, jedan od mogućih ishoda za k=5 dodatnih koraka je: 1112444335. Npr. niz za koji algoritam ne prestaje u k=5 koraku 1112444333 jer nema 5-ice i kada se ona pojavi biti će kraj, i biti će to jedina 5-ica u nizu. Dakako postoje i nizovi koji nisu nikako mogući npr. 1234512345, zbog toga što algoritam završi u 5-om koraku i ne može generirati sljedećih 12345. Pitanje je koliko takvih "dobrih" permutacija ima, tj. one koje zaustavljaju algoritam u k-tom koraku. Ovaj problem veoma se lako rješi s funkcijama izvodnicama, ali još bolje je odmah primijetiti da je taj broj jednak broju surjekcija iz skupa s N+k-1 članova u skup s N-1 članom. Ili bolje rečeno za svaku poziciju u generiranom nizu možemo odabrati N-1 član ali na takav način da do kraja niza tj. do predzadnjeg člana imamo svih N-1 brojeva barem jednom. I taj broj pomnožimo sa N zbog toga što imamo N slučajeva u kojem na kraju niza dolazi po jedan N.

Vjerojatnost da algoritam završi u k-tom koraku:

$$p(X=k)=\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$

Matematičko očekivanje je:

$$E(k)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$

Definiramo vremensku složenost algoritma kao matematičko očekivanje koje ovisi o broju N.

$$f(N)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$

Rezultati

 

Teorijski:

Ograničimo očekivanje:

$$f(N)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}<N \cdot ln(N)$$

Kada se riješimo beskonačne sume tako što zamijenimo ove dvije sume a beskonačna suma je zapravo poznati red i skraćivanjem nejednakosti s N dobije se:

$$\frac{1}{N^{N-1}}\sum_{i=1}^{N}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}} <  \sum_{i=1}^{N}\frac{1}{i} < ln(N) + 1$$

Probajmo izračunati razliku između sume recipročnih brojeva i našeg izraza:

$$\sum_{i=1}^{N}\left [ \frac{1}{i}-\frac{1}{N^{N-1}}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}}\right ] = 1.$$


Dokaz (hvala Maks!):

http://fly.srk.fer.hr/~dsantl/dokaz_rand.pdf
 

Dakle, vremenska složenost ovog algoritma je: $$O(Nlog(N))$$

Eksperimentalno:

Testiranjem algoritma i mjerenjem vremena ili koraka dobiju se pravi rezultati u izvođenju. Kako je algoritam nedeterministički, potrebno je za svaki N rezultate usrednjiti. U nastavku su dati grafovi koji prikazuju koliko koraka je potrebno da bi se algoritam izvršio u ovisnosti broja N. Može se uočiti da je funkcija N ln(N) gornja granica izmjerenih rezultata. Dvije su slike, prva prikazuje srednju vrijednost 50 rezultata za svaki N, a druga 100 rezultata za svaki N.





Sljedeća slika pokazuje kako izgleda teorijska funkcija koja je dobivena (očekivanje) i iz toga se može vidjeti da nejednakost vrijedi na prikazanom intervalu (plava boja je N ln(N), a ljubičasta matematičko očekivanje) :



I za kraj, kolika je vrijednost ovog izraza (barem na prikazanom intervalu):

$$\sum_{i=1}^{N}\left [ \frac{1}{i}-\frac{1}{N^{N-1}}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}}\right ]$$

Bolji algoritam

Napravi se niz od N članova i to tako da je A[i] = i, 1<=i<=N.  Stvorimo novi niz, niz pokazivača (niz indeksa) B[i] = index_od_i, gdje svaki član niza B pamti nekoga iz niza A. Generira se slučajni broj 1 do N i pogleda se na koji broj pokazuje B[ rand() ], to je sada baš broj rand(). U element B[ rand() ] stavi se indeks zadnjeg elementa koji još nije generiran. Sada se generira slučajni broj od 1 do N-1, i odabire se element B[rand], tj. broj A[B[rand()]], taj sigurno nije generiran, i nakon toga se opet u B[rand()] stavi indeks zadnjeg koji nije generiran (najvećeg). U svakom koraku generiramo jedan broj, tako da je složenost očigledna i iznosi O(N) (Uz pretpostavku da je funkcija rand() u O(1)).

Zaključak

Hm... analiza boljeg algoritma je puno kraća i ako sam to znao zašto sam išao raditi ono gore. Pa pokazano je da onaj gornji algoritam uopće nije tako loš kako se čini. A osim toga neki od razloga su to što sam se nadao nećem što će biti fora, a to sam i dobio.

"Ne samo moćno oružje u borbi za opstanak, matematika je simbol naše intelektualne snage i jamstvo da će se ljudski duh vazda boriti za uzvišene ciljeve." - Danilo Blanuša (1903-1987)