Tragičan gubitak. :(
Saša mi je predavao Složenost algoritama i Aritmetičke i algebarske algoritme, te mi je bio u komisiji za diplomski ispit. Kad sam se prijavljivao na doktorske studije, pomogao mi je napisavši pismo preporuke.
Sa Složenosti se i nakon 13 godina još dobro sjećam analize [url=https://en.wikipedia.org/wiki/Kruskal%27s_algorithm]Kruskalovog algoritma[/url] za minimalno razapinjuće stablo u kojem ključnu ulogu igra [url=https://en.wikipedia.org/wiki/Disjoint-set_data_structure]union-find struktura podataka[/url]. U optimalnoj izvedbi, operacije union i find nad [latex]n[/latex] elemenata imaju amortiziranu složenost [latex]O(\log^* n)[/latex], pri čemu je [latex]\log^* n[/latex] [url=https://en.wikipedia.org/wiki/Iterated_logarithm]iterirani logaritam[/url]. Sjećam se kako je Saša entuzijastično objašnjavao da iterirani logaritam nevjerojatno sporo raste -- za sve praktične potrebe je konstantan. Otada ne mogu pomisliti na Kruskalov algoritam i union-find strukturu, a da se ne sjetim i Saše.
Tragičan gubitak.
Saša mi je predavao Složenost algoritama i Aritmetičke i algebarske algoritme, te mi je bio u komisiji za diplomski ispit. Kad sam se prijavljivao na doktorske studije, pomogao mi je napisavši pismo preporuke.
Sa Složenosti se i nakon 13 godina još dobro sjećam analize Kruskalovog algoritma za minimalno razapinjuće stablo u kojem ključnu ulogu igra union-find struktura podataka. U optimalnoj izvedbi, operacije union i find nad elemenata imaju amortiziranu složenost , pri čemu je iterirani logaritam. Sjećam se kako je Saša entuzijastično objašnjavao da iterirani logaritam nevjerojatno sporo raste – za sve praktične potrebe je konstantan. Otada ne mogu pomisliti na Kruskalov algoritam i union-find strukturu, a da se ne sjetim i Saše.
_________________
I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.