Java - Complexidade de espaço com variável - java, complexidade de espaço

A complexidade espacial é aqui O (n)? Como se k aumenta em 5, minha variável p também aumentaria em 5.

Tudo o que esse método faz agora é obter o nó em k. Por exemplo: 1-> 5-> 3, quando k = 2, o nó é 5.

public ListNode reverseKGroup(ListNode head, int k) {
int p = 1;

while (p < k) {
if (head.next == null) {
return head;
}
head = head.next;
p++;
}

return head
}

Respostas:

Considerando estritamente seu algoritmo, ele tem uma complexidade de espaço O (1). Sua entrada é um cabeçalho de uma lista e um número k, mas o seu algoritmo não consome mais espaço do que apenas uma referência head e um número p. Na minha opinião, a lista existente não pertence à complexidade do seu método, mas sua complexidade de tempo é O (N).

--- responda a pergunta de Theo no comentário:

p é um número (neste caso, do tipo primitivo int, então leva 4 bytes - tamanho constante). E se p aumenta, não significa, leva mais espaço,mas que um número mais alto é armazenado em. p = 5 significa que os bytes seguintes estão definidos: "0,0,0,5", para p = 257, os bytes são definidos: "0,0,1,2". Eu suponho, a JVM armazena a data em ordem de byte big endian, então o primeiro zero "s está representando os bytes maiores. Com little endian, a ordem de byte seria invertida.

Claro, você está certo, que por muito grande N, o inteiro de 32 bits não é suficiente. Portanto, considerando estritamente este fato, os bits O (log (N)) são necessários para armazenar números de até N. Por exemplo. um número 2 ^ 186 precisa de 187 bits para serem armazenados (um 1 e 186 zeros).

Mas, na realidade, quando se trabalha com dados "usuais", você não espera uma quantia tão grande. Como só deve exceder o registro de 32 bits (um int número), você precisaria ter 2 ^ 32 entradas de dados (1 entrada = 4 bytes para uma próxima referência, pelo menos 4 bytes para o valor Object referência, e o tamanho do objeto em si = pelo menos8 bytes), ou seja, 2 ^ 35 bytes = 32 gigabyes. Portanto, quando um número é usado, geralmente é considerado uma complexidade espacial constante. Depende da tarefa e das circunstâncias.

Dependendo se você considera pré-existenteestrutura parte de sua complexidade de espaço, a complexidade de espaço é O (1) ou O (N), onde N é o comprimento da lista que está sendo operada, uma vez que você não adiciona novos nós e apenas faz referência a nós existentes.

k só importa para a complexidade do tempo.

O único espaço que este algoritmo usa é o espaço para int p, que é constante, independentemente da entrada, então a complexidade do espaço é O (1). A complexidade do tempo é de fato O (N).