O que há com O (1)?

https://stackoverflow.com/questions/332952

22-07-2019
|

Pergunta

Tenho notado um uso muito estranho de O(1) na discussão de algoritmos envolvendo hashing e tipos de pesquisa, geralmente no contexto do uso de um tipo de dicionário fornecido pelo sistema de linguagem, ou usando tipos de dicionário ou array de hash usados usando array -notação de índice.

Basicamente, O(1) significa limitado por um tempo constante e (normalmente) espaço fixo.Algumas operações bastante fundamentais são O(1), embora o uso de linguagens intermediárias e VMs especiais tenda a distorcer o pensamento aqui (por exemplo, como amortizar o coletor de lixo e outros processos dinâmicos sobre o que de outra forma seriam atividades O(1)).

Mas ignorando a amortização de latências, coleta de lixo e assim por diante, ainda não entendo como é que o salto para a suposição de que certas técnicas que envolvem algum tipo de pesquisa podem ser O(1), exceto sob condições muito especiais.

Embora eu já tenha notado isso antes, um exemplo acabou de aparecer no Pergunta Pandincus, "Coleção 'adequada' a ser usada para obter itens em tempo O(1) em C# .NET?".

Como comentei lá, a única coleção que conheço que fornece acesso O(1) como um limite garantido é uma matriz de limite fixo com um valor de índice inteiro.A presunção é que a matriz é implementada por algum mapeamento para memória de acesso aleatório que usa operações O(1) para localizar a célula que possui esse índice.

Para coleções que envolvem algum tipo de pesquisa para determinar a localização de uma célula correspondente para um tipo diferente de índice (ou para uma matriz esparsa com índice inteiro), a vida não é tão fácil.Em particular, se houver colisões e for possível congestionamento, o acesso não será exatamente O(1).E se a coleção for flexível, deve-se reconhecer e amortizar o custo de expansão da estrutura subjacente (como uma árvore ou uma tabela hash) para ~~qual~~ alívio de congestionamento (por exemplo, alta incidência de colisão ou desequilíbrio de árvores).

Eu nunca teria pensado em falar dessas estruturas flexíveis e dinâmicas como O(1).No entanto, eu os vejo oferecidos como soluções O(1) sem qualquer identificação das condições que devem ser mantidas para que o acesso O(1) seja realmente garantido (bem como para que essa constante seja insignificantemente pequena).

A QUESTÃO:Toda essa preparação é realmente para uma pergunta.Qual é a casualidade em torno de O(1) e por que ela é aceita tão cegamente?É reconhecido que mesmo O(1) pode ser indesejavelmente grande, mesmo sendo quase constante?Ou será O(1) simplesmente a apropriação de uma noção de complexidade computacional para uso informal?Estou confuso.

ATUALIZAR:As respostas e comentários apontam onde eu mesmo fui casual ao definir O(1) e consertei isso.Ainda estou procurando boas respostas, e alguns tópicos de comentários são bem mais interessantes do que suas respostas, em alguns casos.

Solução

Meu entendimento é que O(1) não é necessariamente constante;pelo contrário, não depende das variáveis em consideração.Assim, pode-se dizer que uma pesquisa de hash é O(1) em relação ao número de elementos no hash, mas não em relação ao comprimento dos dados que estão sendo hash ou à proporção de elementos por baldes no hash.

O outro elemento de confusão é que a notação O grande descreve um comportamento limitante.Assim, uma função f(N) para pequenos valores de N pode de fato mostrar grande variação, mas você ainda estaria correto em dizer que é O(1) se o limite quando N se aproxima do infinito for constante em relação a N.

Outras dicas

O problema é que as pessoas são muito desleixadas com a terminologia.Existem 3 classes importantes, mas distintas aqui:

O (1) pior caso

Isto é simples - todas as operações não levam mais do que um período de tempo constante no pior dos casos e, portanto, em todos os casos.Acessar um elemento de um array é O(1) pior caso.

O(1) pior caso amortizado

Amortizado significa que nem toda operação é O(1) no pior caso, mas para qualquer sequência de N operações, o custo total da sequência não é O(N) na pior das hipóteses.Isto significa que mesmo que não possamos limitar o custo de qualquer operação única por uma constante, sempre haverá operações “rápidas” suficientes para compensar as operações “lentas”, de modo que o tempo de execução da sequência de operações seja linear. no número de operações.

Por exemplo, o padrão Matriz Dinâmica que dobra sua capacidade quando enche requer O(1) tempo amortizado para inserir um elemento no final, mesmo que algumas inserções exijam O(N) tempo - sempre há o suficiente O(1) inserções que a inserção de N itens sempre leva O(N) tempo total.

O (1) caso médio

Este é o mais complicado.Existem duas definições possíveis de caso médio:um para algoritmos aleatórios com entradas fixas e outro para algoritmos determinísticos com entradas aleatórias.

Para algoritmos aleatórios com entradas fixas, podemos calcular o tempo de execução do caso médio para qualquer entrada, analisando o algoritmo e determinando a distribuição de probabilidade de todos os tempos de execução possíveis e calculando a média dessa distribuição (dependendo do algoritmo, isso pode ou pode não ser possível devido ao problema de parada).

No outro caso, precisamos de uma distribuição de probabilidade sobre as entradas.Por exemplo, se medissemos um algoritmo de classificação, uma dessas distribuições de probabilidade seria a distribuição que tem todos os N!possíveis permutações da entrada são igualmente prováveis.Então, o tempo de execução do caso médio é o tempo médio de execução de todas as entradas possíveis, ponderado pela probabilidade de cada entrada.

Como o assunto desta questão são tabelas hash, que são determinísticas, vou me concentrar na segunda definição de caso médio.Agora, nem sempre podemos determinar a distribuição de probabilidade das entradas porque, bem, poderíamos estar fazendo hash de praticamente qualquer coisa, e esses itens podem vir de um usuário que os digita ou de um sistema de arquivos.Portanto, ao falar sobre tabelas hash, a maioria das pessoas apenas assume que as entradas são bem comportadas e a função hash é bem comportada, de modo que o valor hash de qualquer entrada é essencialmente distribuído aleatoriamente de maneira uniforme ao longo do intervalo de valores hash possíveis.

Reserve um momento e deixe que o último ponto seja absorvido - o O(1) o desempenho de caso médio para tabelas de hash vem da suposição de que todos os valores de hash são distribuídos uniformemente.Se esta suposição for violada (o que normalmente não é, mas certamente pode acontecer e acontece), o tempo de execução não é mais O(1) na média.

Veja também Negação de serviço por complexidade algorítmica.Neste artigo, os autores discutem como exploraram alguns pontos fracos nas funções hash padrão usadas por duas versões do Perl para gerar um grande número de strings com colisões de hash.Armados com esta lista de strings, eles geraram um ataque de negação de serviço em alguns servidores web, alimentando-os com essas strings que resultaram no pior caso. O(N) comportamento nas tabelas hash usadas pelos servidores web.

O(1) significa tempo constante e (normalmente) espaço fixo

Apenas para esclarecer, estas são duas declarações separadas.Você pode ter O(1) no tempo, mas O(n) no espaço ou algo assim.

É reconhecido que mesmo O(1) pode ser indesejavelmente grande, mesmo sendo quase constante?

O(1) pode ser impraticavelmente ENORME e ainda é O(1).Muitas vezes é negligenciado que, se você sabe que terá um conjunto de dados muito pequeno, a constante é mais importante que a complexidade e, para conjuntos de dados razoavelmente pequenos, é um equilíbrio entre os dois.Um algoritmo O(n!) pode superar um O(1) se as constantes e tamanhos dos conjuntos de dados estiverem na escala apropriada.

A notação O() é uma medida da complexidade - não o tempo que um algoritmo levará, ou uma medida pura de quão "bom" é um determinado algoritmo para um determinado propósito.

Entendo o que você está dizendo, mas acho que há algumas suposições básicas subjacentes à afirmação de que pesquisas em uma tabela Hash têm uma complexidade de O(1).

A função hash é razoavelmente projetada para evitar um grande número de colisões.
O conjunto de chaves é distribuído de forma praticamente aleatória ou, pelo menos, não foi projetado propositalmente para fazer com que a função hash tenha um desempenho ruim.

A pior complexidade de uma consulta de tabela Hash é O(n), mas isso é extremamente improvável, dadas as duas suposições acima.

Tabelas hash é uma estrutura de dados que suporta pesquisa e inserção O(1).

Uma tabela hash geralmente possui um par de chave e valor, onde o key é usada como parâmetro para uma função (um função hash) que determinará a localização do valor em sua estrutura de dados interna, geralmente uma matriz.

Como a inserção e a pesquisa dependem apenas do resultado da função hash e não do tamanho da tabela hash nem do número de elementos armazenados, uma tabela hash possui inserção e pesquisa O(1).

Há um embargo, no entanto.Ou seja, à medida que a tabela hash fica cada vez mais cheia, haverá colisões de hash onde a função hash retornará um elemento de um array que já está ocupado.Isso exigirá um resolução de colisão para encontrar outro elemento vazio.

Quando ocorre uma colisão de hash, uma busca ou inserção não pode ser realizada em tempo O(1).No entanto, bons algoritmos de resolução de colisão pode reduzir o número de tentativas para encontrar outro espaço vazio adequado ou aumentando o tamanho da tabela hash pode reduzir o número de colisões em primeiro lugar.

Então, em teoria, apenas uma tabela hash apoiada por um array com um número infinito de elementos e uma função hash perfeita seria capaz de atingir o desempenho O(1), pois essa é a única maneira de evitar colisões de hash que aumentam o número de operações necessárias.Portanto, para qualquer array de tamanho finito será em um momento ou outro menor que O(1) devido a colisões de hash.

Vejamos um exemplo.Vamos usar uma tabela hash para armazenar o seguinte (key, value) pares:

(Name, Bob)
(Occupation, Student)
(Location, Earth)

Implementaremos o back-end da tabela hash com um array de 100 elementos.

O key será usado para determinar um elemento da matriz para armazenar o (key, value) par.Para determinar o elemento, o hash_function será usado:

hash_function("Name") retorna 18
hash_function("Occupation") retorna 32
hash_function("Location") retorna 74.

A partir do resultado acima, atribuiremos o (key, value) pares nos elementos da matriz.

array[18] = ("Name", "Bob")
array[32] = ("Occupation", "Student")
array[74] = ("Location", "Earth")

A inserção requer apenas o uso de uma função hash, e não depende do tamanho da hashtable nem de seus elementos, portanto pode ser realizada em tempo O(1).

Da mesma forma, a busca por um elemento usa a função hash.

Se quisermos procurar a chave "Name", realizaremos um hash_function("Name") para descobrir em qual elemento da matriz reside o valor desejado.

Além disso, a pesquisa não depende do tamanho da tabela hash nem do número de elementos armazenados, portanto, uma operação O(1).

Tudo está bem.Vamos tentar adicionar uma entrada adicional de ("Pet", "Dog").Contudo, há um problema, pois hash_function("Pet") retorna 18, que é o mesmo hash para o "Name" chave.

Portanto, precisaremos resolver essa colisão de hash.Vamos supor que a função de resolução de colisão hash que usamos descobriu que o novo elemento vazio é 29:

array[29] = ("Pet", "Dog")

Como houve uma colisão de hash nesta inserção, nosso desempenho não foi exatamente O(1).

Este problema também surgirá quando tentarmos procurar o "Pet" chave, como tentar encontrar o elemento que contém o "Pet" chave executando hash_function("Pet") sempre retornará 18 inicialmente.

Assim que procurarmos o elemento 18, encontraremos a chave "Name" em vez de "Pet".Quando encontrarmos esta inconsistência, precisaremos resolver a colisão para recuperar o elemento correto que contém o real "Pet" chave.A resolução de uma colisão de hash é uma operação adicional que faz com que a tabela hash não funcione no tempo O(1).

Não posso falar das outras discussões que você viu, mas há pelo menos um algoritmo de hash que é garantido ser O (1).

Hash de cuco mantém uma invariante para que não haja encadeamento na tabela hash.A inserção é amortizada O(1), a recuperação é sempre O(1).Nunca vi uma implementação disso, é algo que foi descoberto recentemente quando eu estava na faculdade.Para conjuntos de dados relativamente estáticos, deve ser um O(1) muito bom, pois calcula duas funções hash, realiza duas pesquisas e sabe imediatamente a resposta.

Veja bem, isso pressupõe que o cálculo do hash também seja O(1).Você poderia argumentar que, para strings de comprimento K, qualquer hash é minimamente O(K).Na realidade, você pode vincular K facilmente, digamos K <1000.OK(K) ~= O(1) para K <1000.

Pode haver um erro conceitual sobre como você entende a notação Big-Oh.O que isso significa é que, dado um algoritmo e um conjunto de dados de entrada, o limite superior para o tempo de execução do algoritmo depende do valor da função O quando o tamanho do conjunto de dados tende ao infinito.

Quando se diz que um algoritmo leva tempo O(n), significa que o tempo de execução para o pior caso de um algoritmo depende linearmente do tamanho do conjunto de entradas.

Quando um algoritmo leva tempo O(1), a única coisa que isso significa é que, dada uma função T(f) que calcula o tempo de execução de uma função f(n), existe um número natural positivo k tal que T(f) < k para qualquer entrada n.Essencialmente, isso significa que o limite superior para o tempo de execução de um algoritmo não depende de seu tamanho e tem um limite fixo e finito.

Agora, isso não significa de forma alguma que o limite seja pequeno, apenas que é independente do tamanho do conjunto de entradas.Portanto, se eu definir artificialmente um limite k para o tamanho de um conjunto de dados, sua complexidade será O(k) == O(1).

Por exemplo, procurar uma instância de um valor em uma lista vinculada é uma operação O(n).Mas se eu disser que uma lista tem no máximo 8 elementos, então O(n) vira O(8) vira O(1).

Neste caso, se utilizamos uma estrutura de dados trie como dicionário (uma árvore de caracteres, onde o nó folha contém o valor da string usada como chave), se a chave for limitada, então seu tempo de busca pode ser considerado O( 1) (Se eu definir um campo de caracteres como tendo no máximo k caracteres de comprimento, o que pode ser uma suposição razoável para muitos casos).

Para uma tabela hash, contanto que você assuma que a função hash é boa (distribuída aleatoriamente) e suficientemente esparsa para minimizar colisões, e o rehashing seja executado quando a estrutura de dados for suficientemente densa, você pode de fato considerá-la um O(1 ) estrutura de tempo de acesso.

Concluindo, o tempo O(1) pode ser superestimado para muitas coisas.Para grandes estruturas de dados, a complexidade de uma função hash adequada pode não ser trivial, e existem casos extremos suficientes onde a quantidade de colisões a leva a se comportar como uma estrutura de dados O(n), e o rehashing pode se tornar proibitivamente caro.Nesse caso, uma estrutura O(log(n)) como uma AVL ou uma árvore B pode ser uma alternativa superior.

Em geral, acho que as pessoas os usam comparativamente, sem levar em conta a exatidão.Por exemplo, estruturas de dados baseadas em hash são O(1) (média) pesquisadas se bem projetadas e você tiver um bom hash.Se tudo for hash para um único bucket, então será O(n).Geralmente, embora se use um bom algoritmo e as chaves sejam razoavelmente distribuídas, é conveniente falar sobre isso como O(1) sem todas as qualificações.Da mesma forma com listas, árvores, etc.Temos em mente certas implementações e é simplesmente mais conveniente falar sobre elas, ao discutir generalidades, sem ressalvas.Se, por outro lado, estamos discutindo implementações específicas, provavelmente vale a pena ser mais preciso.

As pesquisas de HashTable são O(1) em relação ao número de itens na tabela, porque não importa quantos itens você adicione à lista, o custo de hash de um único item é praticamente o mesmo, e a criação do hash dirá você o endereço do item.

Para responder por que isso é relevante:o OP perguntou por que O(1) parecia ser usado tão casualmente quando, em sua mente, obviamente não poderia ser aplicado em muitas circunstâncias.Esta resposta explica que o tempo O(1) é realmente possível nessas circunstâncias.

Na prática, as implementações de tabelas hash não são "exatamente" O(1) em uso; se você testar uma, descobrirá que elas têm uma média de 1,5 pesquisas para encontrar uma determinada chave em um grande conjunto de dados

(devido ao fato de que colisões FAZER ocorrer, e após a colisão, um local diferente deve ser atribuído)

Além disso, na prática, HashMaps são apoiados por arrays com um tamanho inicial, que "cresce" para o dobro do tamanho quando atinge 70% de preenchimento em média, o que proporciona um espaço de endereçamento relativamente bom.Após 70% de plenitude, as taxas de colisão aumentam mais rapidamente.

A teoria do Big O afirma que se você tiver um algoritmo O(1), ou mesmo um algoritmo O(2), o fator crítico é o grau de relação entre o tamanho do conjunto de entradas e as etapas para inserir/buscar um deles.O(2) ainda é um tempo constante, então apenas o aproximamos como O(1), porque significa mais ou menos a mesma coisa.

Na realidade, existe apenas uma maneira de ter uma "tabela hash perfeita" com O(1), e isso requer:

Um gerador de chave hash global perfeito
Um espaço de endereçamento ilimitado.

( Caso de exceção:se você puder calcular antecipadamente todas as permutações de chaves permitidas para o sistema, e seu espaço de endereço de armazenamento de apoio de destino for definido para ser o tamanho onde ele pode conter todas as chaves permitidas, então você pode ter um hash perfeito, mas é um Perfeição de "domínio limitado")

Dada uma alocação de memória fixa, não é nem um pouco plausível ter isso, porque seria assumido que você tem alguma maneira mágica de empacotar uma quantidade infinita de dados em uma quantidade fixa de espaço sem perda de dados, e isso é logisticamente impossível .

Então, retrospectivamente, obter O(1.5) que ainda é um tempo constante, em uma quantidade finita de memória, mesmo com um gerador de chave hash relativamente ingênuo, considero muito incrível.

Nota sufixo Observe que uso O(1,5) e O(2) aqui.Na verdade, eles não existem no Big-O.Isso é apenas o que as pessoas que não sabem muito presumem ser a razão.

Se algo leva 1,5 passos para encontrar uma chave, ou 2 passos para encontrar essa chave, ou 1 passo para encontrar essa chave, mas o número de passos nunca excede 2 e se leva 1 passo ou 2 é completamente aleatório, então ainda é Grande-O de O (1).Isto porque não importa como muitos itens para você adicionar ao tamanho do conjunto de dados, ele ainda mantém as <2 etapas.Se para todas as tabelas > 500 chaves são necessárias 2 etapas, então você pode assumir que essas 2 etapas são na verdade uma etapa com 2 partes, ...que ainda é O (1).

Se você não pode fazer essa suposição, então você não está pensando no Big-O, porque então você deve usar o número que representa o número de etapas computacionais finitas necessárias para fazer tudo e "uma etapa" não tem sentido para você.Basta entrar na sua cabeça que existe NÃO correlação direta entre Big-O e número de ciclos de execução envolvidos.

O(1) significa, exatamente, que a complexidade de tempo do algoritmo é limitada por um valor fixo.Isso não significa que seja constante, apenas que é limitado independentemente dos valores de entrada.Estritamente falando, muitos algoritmos de tempo supostamente O(1) não são realmente O(1) e são tão lentos que são limitados por todos os valores práticos de entrada.

Sim, a coleta de lixo afeta a complexidade assintótica dos algoritmos executados na área de coleta de lixo.Não é isento de custos, mas é muito difícil de analisar sem métodos empíricos, porque os custos de interação não são composicionais.

O tempo gasto na coleta de lixo depende do algoritmo usado.Normalmente, os coletores de lixo modernos alternam os modos conforme a memória é preenchida para manter esses custos sob controle.Por exemplo, uma abordagem comum é usar um coletor de cópias estilo Cheney quando a pressão da memória é baixa porque paga um custo proporcional ao tamanho do set ao vivo em troca de usar mais espaço, e mudar para um coletor de marcação e varredura quando a pressão da memória torna-se maior, pois ainda paga custo proporcional ao conjunto ativo para marcação e a todo o heap ou conjunto morto para varredura.No momento em que você adiciona marcação de cartão e outras otimizações, etc.o pior caso de custos para um coletor de lixo prático pode, na verdade, ser um pouco pior, captando um fator logarítmico extra para alguns padrões de uso.

Então, se você alocar uma grande tabela hash, mesmo se você acessá-la usando pesquisas O(1) durante todo o seu tempo de vida, se você fizer isso em um ambiente de coleta de lixo, ocasionalmente o coletor de lixo percorrerá todo o array, porque ele é o tamanho O(n) e você pagará esse custo periodicamente durante a coleta.

A razão pela qual geralmente deixamos isso de fora da análise de complexidade de algoritmos é que a coleta de lixo interage com seu algoritmo de maneiras não triviais.O custo desse custo depende muito do que mais você está fazendo no mesmo processo, portanto a análise não é composicional.

Além disso, acima e além da cópia vs.compacto vs.problema de marcação e varredura, os detalhes de implementação podem afetar drasticamente as complexidades resultantes:

Coletores de lixo incrementais que rastreiam pedaços sujos, etc.pode praticamente fazer com que essas retravessas maiores desapareçam.
Depende se o seu GC funciona periodicamente com base no horário do relógio ou é proporcional ao número de alocações.
Se um algoritmo de estilo de marcação e varredura é simultâneo ou para o mundo
Se ele marca as novas alocações em preto, se as deixa brancas até colocá-las em um recipiente preto.
O fato de sua linguagem admitir modificações de ponteiros pode permitir que alguns coletores de lixo funcionem em uma única passagem.

Finalmente, ao discutir um algoritmo, estamos discutindo um espantalho.Os assintóticos nunca incorporarão totalmente todas as variáveis do seu ambiente.Raramente você implementa todos os detalhes de uma estrutura de dados conforme projetado.Você pega emprestado um recurso aqui e ali, coloca uma tabela hash porque precisa de acesso rápido e não ordenado à chave, usa uma localização de união sobre conjuntos disjuntos com compactação de caminho e união por classificação para mesclar regiões de memória ali porque você não pode dar-se ao luxo de pagar um custo proporcional ao tamanho das regiões quando você as fundir ou o que quer que seja.Essas estruturas são pensadas como primitivas e os assintóticos ajudam no planejamento de características gerais de desempenho para a estrutura 'em geral', mas o conhecimento de quais são as constantes também é importante.

Você pode implementar essa tabela hash com características assintóticas perfeitamente O(1), apenas não use coleta de lixo;mapeie-o na memória a partir de um arquivo e gerencie-o você mesmo.Você provavelmente não gostará das constantes envolvidas.

Acho que quando muitas pessoas usam o termo "O (1)", elas implicitamente têm em mente uma constante "pequena", seja lá o que "pequeno" signifique em seu contexto.

Você tem que fazer toda essa grande análise com contexto e bom senso.Pode ser uma ferramenta extremamente útil ou ridícula, dependendo de como você a utiliza.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow