2
Jaka jest najgorsza złożoność sita z polem liczbowym?
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(logN)13(loglogN)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …