Por que log (n) é uma função construtível em espaço?

8

De acordo com "Função construtiva" , Wikipedia:

Na teoria da complexidade , uma função construtível no tempo é uma função f de números naturais para números naturais com a propriedade de que f ( n ) pode ser construída a partir de n por uma máquina de Turing no tempo da ordem f ( n ).

Mas não é mapeado para números naturais, mas para números reais.registro(n)

Por que no entanto, é uma função construtível em espaço?registro(n)

Máxima
fonte

Respostas:

12

Porque quando escrevemos , isso ocorre em um contexto em que não importa (por exemplo, limites do Landau) ou com o significado implícito de ou .registronregistronregistron

? Certamente não faz sentido falar sobre funções construtivas com alcance real, eu diria que sua fonte está falando sobre ou .registronregistron

ordenação rápida
fonte