ďťż
  Złozoność sita Eratostenesa


Rafał Nowak - 3 cze 2009, o 13:18
" />Czy ktoś wie, gdzie mogę znaleźć to, że złośoność sita wynosi O(n log(log n))?



Mateusz Gołębiewski - 3 cze 2009, o 19:02
" />Nie wynosi.
Złożoność sita to O((n log n)(log log n))
http://en.wikipedia.org/wiki/Sieve_of_E ... complexity

Jest za to sito liniowe (linear sieve)
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0011.php

oraz sito Atkina-Bernsteina działające w złożoności O(n/log log n)
http://pl.wikipedia.org/wiki/Sito_Atkina
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0012.php

dziadek Google wie wszystko :) ale lubi sciągać z wikipedii :P


Rafał Nowak - 3 cze 2009, o 20:04
" />


Paweł Gawrychowski - 4 cze 2009, o 14:13
" />



Mateusz Gołębiewski - 4 cze 2009, o 15:46
" />


Jakub Łopuszański - 8 cze 2009, o 11:00
" />
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • albionteam.htw.pl
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • cichooo.htw.pl
    		•