Algorytmy ze złożonością O (sqrt (N)) SPACE?

13

Czy są jakieś znane algorytmy dla sformułowanych problemów, które wymagają złożoności SPACE dla O (sqrt (N))? Wiem, że istnieją algorytmy o złożoności czasowej „wielkiej O”.

vawd_gandi
źródło
W przypadku ważnego problemu o nazwie 3sum występuje następujący kompromis. Jeśli chcesz mieć czas , najbardziej znaną złożonością przestrzeni jest O ( O(n2). Zobaczarxiv.org/abs/1605.07285O(n)
eig

Odpowiedzi:

15

przestrzeń jest nieco niezwykła; najbardziej prawdopodobną przyczyną pojawienia się takiej złożoności jest tak zwanespotkanie w środkowymschemacie.n

Dwa godne uwagi przykłady u szczytu mojej głowy to klasyczne sito Eratostenesa i algorytm gigantycznych kroków dziecka dla dyskretnego logarytmu w skończonej grupie.

szybkie sortowanie
źródło