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
źródło
Odpowiedzi:
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.
źródło