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

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”.

complexity-theory asymptotics space-complexity

— 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 (n^{2})

$O(n^2)$

. Zobaczarxiv.org/abs/1605.07285

O (\sqrt{n})

$O(\sqrt{n})$

— eig

Odpowiedzi:

przestrzeń jest nieco niezwykła; najbardziej prawdopodobną przyczyną pojawienia się takiej złożoności jest tak zwanespotkanie w środkowymschemacie. $\sqrt{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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.