Algoritmo no local - In-place algorithm

Em ciência da computação , um algoritmo in-loco é um algoritmo que transforma a entrada sem nenhuma estrutura de dados auxiliar . No entanto, uma pequena quantidade de espaço de armazenamento extra é permitida para variáveis ​​auxiliares. A entrada geralmente é substituída pela saída à medida que o algoritmo é executado. Um algoritmo local atualiza sua sequência de entrada apenas por meio da substituição ou troca de elementos. Um algoritmo que não está no local é às vezes chamado de não no local ou fora do local .

No local pode ter significados ligeiramente diferentes. Em sua forma mais restrita, o algoritmo pode ter apenas uma quantidade constante de espaço extra , contando tudo, incluindo chamadas de função e ponteiros . No entanto, essa forma é muito limitada, pois simplesmente ter um índice com uma matriz de comprimento n requer O (log n ) bits. De forma mais ampla, no local significa que o algoritmo não usa espaço extra para manipular a entrada, mas pode exigir um espaço extra pequeno, embora não constante, para sua operação. Normalmente, esse espaço é O (log n ) , embora às vezes qualquer coisa em O ( n ) seja permitido. Observe que a complexidade do espaço também tem opções variadas quanto a contar ou não os comprimentos do índice como parte do espaço usado. Freqüentemente, a complexidade do espaço é dada em termos do número de índices ou ponteiros necessários, ignorando seu comprimento. Neste artigo, nos referimos à complexidade do espaço total ( DSPACE ), contando os comprimentos do ponteiro. Portanto, os requisitos de espaço aqui têm um fator log n extra em comparação com uma análise que ignora o comprimento dos índices e indicadores.

Um algoritmo pode ou não contar a saída como parte de seu uso de espaço. Como os algoritmos no local geralmente sobrescrevem sua entrada com saída, nenhum espaço adicional é necessário. Ao gravar a saída na memória somente para gravação ou em um fluxo, pode ser mais apropriado considerar apenas o espaço de trabalho do algoritmo. Em aplicações teóricas, como reduções de espaço de log , é mais comum sempre ignorar o espaço de saída (nesses casos, é mais essencial que a saída seja somente gravação ).

Exemplos

Dada uma matriz a de n itens, suponha que queiramos uma matriz que contenha os mesmos elementos em ordem reversa e descartar o original. Uma maneira aparentemente simples de fazer isso é criar um novo array de tamanho igual, preenchê-lo com cópias ana ordem apropriada e, em seguida, excluí-lo a.

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

Infelizmente, isso requer O ( n ) espaço extra para ter os arrays ae bdisponíveis simultaneamente. Além disso, a alocação e a desalocação costumam ser operações lentas. Já que não precisamos mais a, podemos substituí-lo com sua própria reversão usando este algoritmo no local que só precisará de um número constante (2) de inteiros para as variáveis ​​auxiliares ie tmp, não importa o tamanho do array.

 function reverse_in_place(a[0..n-1])
     for i from 0 to floor((n-2)/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

Como outro exemplo, muitos algoritmos de classificação reorganizam as matrizes em ordem de classificação no local, incluindo: classificação por bolha , classificação por pente , classificação por seleção , classificação por inserção , classificação heapsort e classificação Shell . Esses algoritmos requerem apenas alguns ponteiros, portanto, sua complexidade de espaço é O (log n ) .

O Quicksort opera no local nos dados a serem classificados. No entanto, o quicksort requer ponteiros de espaço de pilha O (log n ) para manter o controle dos subarranjos em sua estratégia de divisão e conquista . Conseqüentemente, o quicksort precisa de espaço adicional O (log ² n ) . Embora esse espaço não constante tecnicamente tire o quicksort da categoria no local, o quicksort e outros algoritmos que precisam apenas de O (log n ) ponteiros adicionais são geralmente considerados algoritmos no local.

A maioria dos algoritmos de seleção também está pronta, embora alguns reorganizem consideravelmente a matriz de entrada no processo de encontrar o resultado final de tamanho constante.

Alguns algoritmos de manipulação de texto, como corte e reverso, podem ser executados no local.

Em complexidade computacional

Na teoria da complexidade computacional , a definição estrita de algoritmos no local inclui todos os algoritmos com complexidade de espaço O (1) , a classe DSPACE (1). Esta classe é muito limitada; é igual às línguas regulares . Na verdade, nem mesmo inclui nenhum dos exemplos listados acima.

Normalmente consideramos algoritmos em L , a classe de problemas que requer O (log n ) espaço adicional, para estar no lugar. Esta classe está mais de acordo com a definição prática, pois permite números de tamanho n como ponteiros ou índices. Essa definição expandida ainda exclui quicksort, no entanto, por causa de suas chamadas recursivas.

Identificar os algoritmos no local com L tem algumas implicações interessantes; por exemplo, significa que há um algoritmo local (bastante complexo) para determinar se existe um caminho entre dois nós em um grafo não direcionado , um problema que requer O ( n ) espaço extra usando algoritmos típicos, como pesquisa em profundidade (um bit visitado para cada nó). Isso, por sua vez, produz algoritmos no local para problemas como determinar se um gráfico é bipartido ou testar se dois gráficos têm o mesmo número de componentes conectados . Veja SL para mais informações.

Papel da aleatoriedade

Em muitos casos, os requisitos de espaço de um algoritmo podem ser drasticamente cortados usando um algoritmo aleatório . Por exemplo, digamos que desejamos saber se dois vértices em um gráfico de n vértices estão no mesmo componente conectado do gráfico. Não existe um algoritmo simples e determinístico conhecido para determinar isso, mas se simplesmente começarmos em um vértice e executarmos um passeio aleatório de cerca de 20 n ³ passos, a chance de tropeçarmos no outro vértice, desde que seja no mesmo componente é muito alto. Da mesma forma, existem algoritmos simples aleatórios no local para o teste de primalidade, como o teste de primalidade de Miller-Rabin , e também existem algoritmos simples de fatoração aleatória no local, como o algoritmo rho de Pollard . Veja RL e BPL para mais discussão sobre este fenômeno.

Em programação funcional

Linguagens de programação funcional geralmente desencorajam ou não suportam algoritmos explícitos no local que sobrescrevem dados, uma vez que esse é um tipo de efeito colateral ; em vez disso, eles apenas permitem que novos dados sejam construídos. No entanto, bons compiladores de linguagem funcional freqüentemente reconhecerão quando um objeto muito semelhante a um existente é criado e então o antigo é jogado fora, e irão otimizar isso em uma simples mutação "por baixo do capô".

Observe que, em princípio, é possível construir cuidadosamente algoritmos no local que não modificam os dados (a menos que os dados não estejam mais sendo usados), mas isso raramente é feito na prática. Veja estruturas de dados puramente funcionais .

Veja também

• Tabela de algoritmos de classificação no local e não no local

Referências