4
Złożoność czasowa algorytmu Sieve of Eratostenes
Z Wikipedii: Złożoność algorytmu to O(n(logn)(loglogn))operacje bitowe. Jak do tego doszedłeś? To, że złożoność obejmuje ten loglogntermin, mówi mi, że sqrt(n)gdzieś jest. Załóżmy, że uruchamiam sito na pierwszych 100 liczbach ( n = 100), zakładając, że oznaczenie liczb jako złożonych zajmuje stały czas (implementacja tablicy), liczba razy, której użyjemy, mark_composite()byłaby …