Existem casos em que você prefere um algoritmo de complexidade de tempo grande maior que o menor?

242

Existem casos em que você prefere O(log n)complexidade de O(1)tempo a complexidade de tempo? Ou O(n)para O(log n)?

Você tem algum exemplo?

V.Leymarie
fonte
67
Eu preferiria um O(log n)algoritmo para um O(1)algoritmo de se compreender o primeiro, mas não o último ...
Codor
14
Há toneladas de estruturas de dados impraticáveis ​​com O (1) operações da ciência da computação teórica. Um exemplo seria select () em vetores de bits, que pode ser suportado em o (n) espaço extra e O (1) por operação, usando 5 camadas de indireção. Busca binária simples combinado com O (1) posto () acaba por ser mais rápido na prática, de acordo com o autor da Biblioteca Estrutura sucinta Dados
Niklas B.
17
Baixa complexidade assintótica não garante tempos de execução mais rápidos. Multiplicação da matriz de pesquisa para um exemplo concreto.
Connor Clark
54
Além disso ... qualquer algoritmo pode ser convertido em O (1), dada uma pesquisa de tabela suficientemente grande;) #
Connor Clark
19
@ Hoten - Isso supõe que a pesquisa da tabela seja O (1), o que não é um dado para o tamanho das tabelas que você está falando! :)
Jander

Respostas:

267

Pode haver muitos motivos para preferir um algoritmo com maior complexidade de tempo O maior que o mais baixo:

  • Na maioria das vezes, é mais difícil conseguir uma complexidade menor de grande O e requer implementação qualificada, muito conhecimento e muitos testes.
  • big-O oculta os detalhes sobre uma constante : o algoritmo que executa 10^5é melhor do ponto de vista do big-O que 1/10^5 * log(n)( O(1)vs O(log(n)), mas, para o mais razoável, no primeiro executa melhor. Por exemplo, a melhor complexidade para multiplicação de matrizes é O(n^2.373)mas a constante é tão alta que nenhuma biblioteca computacional (que eu saiba) a utiliza.
  • big-O faz sentido quando você calcula algo grande. Se você precisar classificar uma matriz de três números, importa muito pouco se você usa O(n*log(n))ou O(n^2)algoritmo.
  • Às vezes, a vantagem da complexidade do tempo em minúsculas pode ser realmente insignificante. Por exemplo, existe uma árvore de tango da estrutura de dados que fornece uma O(log log N)complexidade de tempo para encontrar um item, mas também há uma árvore binária que encontra o mesmo em O(log n). Mesmo para grandes números da n = 10^20diferença é insignificante.
  • complexidade do tempo não é tudo. Imagine um algoritmo que é executado O(n^2)e requer O(n^2)memória. Pode ser preferível o O(n^3)tempo e o O(1)espaço quando n não for realmente grande. O problema é que você pode esperar por um longo tempo, mas duvido que possa encontrar uma RAM grande o suficiente para usá-la com seu algoritmo
  • paralelização é uma boa característica em nosso mundo distribuído. Existem algoritmos que são facilmente paralelizáveis ​​e existem alguns que não são paralelos. Às vezes, faz sentido executar um algoritmo em 1000 máquinas comuns com uma complexidade maior do que usar uma máquina com uma complexidade um pouco melhor.
  • em alguns lugares (segurança), uma complexidade pode ser um requisito. Ninguém quer ter um algoritmo de hash capaz de fazer hash incrivelmente rápido (porque outras pessoas podem fazer força bruta com você muito mais rápido)
  • embora isso não esteja relacionado à mudança de complexidade, mas algumas das funções de segurança devem ser escritas de maneira a evitar ataques de tempo . Eles geralmente permanecem na mesma classe de complexidade, mas são modificados de uma maneira que sempre leva a pior situação para fazer alguma coisa. Um exemplo é comparar que as strings são iguais. Na maioria dos aplicativos, faz sentido interromper rapidamente se os primeiros bytes forem diferentes, mas em segurança você ainda esperará o final contar as más notícias.
  • alguém patenteou o algoritmo de menor complexidade e é mais econômico para uma empresa usar maior complexidade do que pagar dinheiro.
  • alguns algoritmos se adaptam bem a situações particulares. A classificação por inserção, por exemplo, possui uma complexidade de tempo média O(n^2)pior que a quicksort ou a fusão, mas como algoritmo on - line pode classificar com eficiência uma lista de valores à medida que são recebidos (como entrada do usuário), onde a maioria dos outros algoritmos só pode operar com eficiência em uma lista completa de valores.
Salvador Dalí
fonte
6
Além disso, já vi algumas vezes que as pessoas estavam focadas no grande O do algoritmo central, mas ignorando os custos de instalação. Construir uma tabela de hash, por exemplo, pode ser mais caro do que passar por uma matriz linearmente se você não precisar fazer isso repetidamente. De fato, devido à forma como as CPUs modernas são construídas, mesmo algo como a pesquisa binária pode ser tão rápido em matrizes classificadas quanto uma pesquisa linear - o perfil é uma necessidade.
Luaan
@Luaan "De fato, devido à maneira como as CPUs modernas são construídas, mesmo algo como a pesquisa binária pode ser tão rápida em matrizes classificadas quanto uma pesquisa linear - o perfil é uma necessidade." Interessante! Você pode explicar como a pesquisa binária e a pesquisa linear podem levar a mesma quantidade de tempo em uma CPU moderna?
DJG 12/12
3
@Luaan - Não importa, encontrei o seguinte: schani.wordpress.com/2010/04/30/linear-vs-binary-search
DJG
2
@ DenisdeBernardy: Não, na verdade não. Eles poderiam ser algoritmos em P. E mesmo que não fossem, sob definições razoáveis ​​do que significa paralelizar, isso também não implicaria P! = NP. Lembre-se também de que pesquisar o espaço de possíveis execuções de uma máquina de turing não determinística é bastante paralelamente agradável.
Einpoklum
228

Sempre existe a constante oculta, que pode ser menor no algoritmo O (log n ). Portanto, ele pode trabalhar mais rápido na prática para dados da vida real.

Há também preocupações com espaço (por exemplo, rodando em uma torradeira).

Também há preocupação com o tempo do desenvolvedor - O (log n ) pode ser 1000 × mais fácil de implementar e verificar.

Alistra
fonte
Bom obrigado. Eu estava pensando que poderia também valer a pena considerar a O (log n) algoritmo para garantir a estabilidade do programa (por exemplo, árvores binárias auto-equilibrado)
V.Leymarie
16
Um exemplo em que posso pensar: para uma pequena matriz classificada, seria mais fácil e mais compacto para o programador implementar uma função de pesquisa binária do que escrever uma implementação completa do mapa de hash e usá-la.
Coronel Thirty Two
5
Um exemplo de complexidade: encontrar a mediana de uma lista não classificada é fácil de fazer em O (n * log n), mas difícil de fazer em O (n).
Paul Draper
1
-1, não coloque toras na sua torradeira ... Brincadeiras à parte, isso é verdade. lg né tão, tão, tão perto kpara grande nque a maioria das operações nunca notar a diferença.
corsiKa
3
Há também o fato de que as complexidades algorítmicas com as quais a maioria das pessoas está familiarizada não levam em consideração os efeitos do cache. Procurar algo em uma árvore binária é O (log2 (n)) de acordo com a maioria das pessoas, mas, na realidade, é muito pior porque as árvores binárias têm uma localidade ruim.
Doval
57

Estou surpreso que ninguém tenha mencionado aplicativos vinculados à memória ainda.

Pode haver um algoritmo que tenha menos operações de ponto flutuante devido à sua complexidade (ou seja, O (1) < O (log n )) ou porque a constante na frente da complexidade é menor (ou seja, 2 n 2 <6 n 2 ) . Independentemente disso, você ainda pode preferir o algoritmo com mais FLOP se o algoritmo FLOP inferior for mais vinculado à memória.

O que quero dizer com "ligado à memória" é que você geralmente acessa dados que estão constantemente fora do cache. Para buscar esses dados, você precisa extrair a memória do espaço de memória real para o cache antes de poder executar sua operação nele. Essa etapa de busca geralmente é bastante lenta - muito mais lenta que a sua própria operação.

Portanto, se o seu algoritmo exigir mais operações (ainda que essas operações sejam executadas em dados que já estão no cache [e, portanto, nenhuma busca é necessária]), ainda assim o desempenho do algoritmo será menor com menos operações (que devem ser executadas fora do prazo de validade). -cache data [e, portanto, requer uma busca]) em termos de tempo real da parede.

NoseKnowsAll
fonte
1
Alistra abordou esta indiretamente ao falar sobre "questões de espaço"
Zach Saucier
2
Uma quantidade enorme de erros de cache apenas multiplica a execução final por um valor constante (que não é maior que 8 para a CPU de 3,2 GHz e 4 núcleos com RAM de 1,6 GHz, geralmente é muito menor), por isso é contada como uma constante fixa nas grandes -O notação. Portanto, a única coisa que o cache não causa é mover o limite de n onde a solução O (n) começa a ser mais lenta que a solução O (1).
Marian Spanik
1
@MarianSpanik Você está certo, é claro. Mas esta pergunta pediu uma situação onde nós preferimos O(logn)mais O(1). Você poderia facilmente imaginar uma situação em que, para todo o possível n, o aplicativo menos vinculado à memória seria executado em tempo de parede mais rápido, mesmo com uma complexidade mais alta.
NoseKnowsAll
@MarianSpanik não é um cache que falta até 300 ciclos de clock? De onde vêm os 8?
que você
43

Em contextos em que a segurança dos dados é uma preocupação, um algoritmo mais complexo pode ser preferível a um algoritmo menos complexo se o algoritmo mais complexo tiver melhor resistência a ataques de tempo .

Kevin K
fonte
6
Enquanto o que você disse é verdade, nesse caso, um algoritmo executando em O (1) é por definição invulnerável a ataques de tempo.
Justin Lessard
17
@JustinLessard: Ser O (1) significa que existe algum tamanho de entrada após o qual o tempo de execução do algoritmo é limitado por uma constante. O que acontece abaixo desse limite é desconhecido. Além disso, o limite pode nem ser atingido para qualquer uso do algoritmo no mundo real. O algoritmo pode ser linear e, assim, vazar informações sobre o comprimento da entrada, por exemplo.
Jörg W Mittag
12
O tempo de execução também pode variar de maneiras diferentes, enquanto ainda está sendo limitado. Se o tempo de execução é proporcional a (n mod 5) + 1, ainda é O(1), mas revela informações sobre n. Portanto, um algoritmo mais complexo com tempo de execução mais suave pode ser preferível, mesmo que possa ser assintoticamente (e possivelmente até na prática) mais lento.
Christian Semrau
É basicamente por isso que o bcrypt é considerado bom; torna as coisas mais lentas
David diz Reinstate Monica
@DavidGrinberg Essa é a razão pela qual o bcrypt é usado e se encaixa na pergunta. Mas isso não tem relação com essa resposta, que fala sobre ataques cronometrados.
Christian Semrau
37

Alistra acertou em cheio, mas falhou em fornecer exemplos, assim o farei.

Você tem uma lista de 10.000 códigos UPC para o que sua loja vende. UPC de 10 dígitos, número inteiro para preço (preço em centavos) e 30 caracteres de descrição para o recebimento.

Abordagem O (log N): você tem uma lista classificada. 44 bytes se ASCII, 84 se Unicode. Como alternativa, trate o UPC como um int64 e você obterá 42 e 72 bytes. 10.000 registros - no caso mais alto, você está olhando um pouco menos de um megabyte de armazenamento.

O (1): Não armazene o UPC, mas use-o como uma entrada na matriz. No caso mais baixo, você está vendo quase um terço de um terabyte de armazenamento.

Qual abordagem você usa depende do seu hardware. Na maioria das configurações modernas razoáveis, você usará a abordagem de log N. Posso imaginar que a segunda abordagem é a resposta certa, se por algum motivo você estiver executando em um ambiente em que a RAM é criticamente curta, mas você tem bastante armazenamento em massa. Um terço de um terabyte em um disco não é grande coisa, obter seus dados em uma sonda do disco vale alguma coisa. A abordagem binária simples leva 13 em média. (Observe, no entanto, que ao agrupar suas chaves, você pode reduzir isso para 3 leituras garantidas e, na prática, você armazenaria em cache a primeira.)

Loren Pechtel
fonte
2
Estou um pouco confuso aqui. Você está falando sobre a criação de uma matriz de 10 bilhões de entradas (a maioria das quais será indefinida) e o tratamento do UPC como um índice nessa matriz?
David Z
7
@DavidZ Yes. Se você usar uma matriz esparsa, poderá não obter O (1), mas ele usará apenas 1 MB de memória. Se você usar uma matriz real, terá acesso O (1) garantido, mas ele usará 1/3 TB de memória.
Navin
Em um sistema moderno, ele usará 1/3 TB de espaço de endereço, mas isso não significa que chegará perto da quantidade de memória de backup alocada. Os sistemas operacionais mais modernos não confirmam armazenamento para alocações até que precisem. Ao fazer isso, você está basicamente ocultando uma estrutura de pesquisa associativa para seus dados dentro do sistema de memória virtual de SO / hardware.
Phil Miller
@Novelocrat True, mas se você estiver fazendo isso na velocidade da RAM, o tempo de pesquisa não importará, não há razão para usar 40mb em vez de 1mb. A versão do array só faz sentido quando o acesso ao armazenamento é caro - você está indo para o disco.
Loren Pechtel
1
Ou quando essa não é uma operação crítica para o desempenho, e o tempo do desenvolvedor é caro - dizer malloc(search_space_size)e assinar o que ele retorna é o mais fácil possível.
Phil Miller
36

Considere uma árvore vermelha e preta. Possui acesso, pesquisa, inserção e exclusão de O(log n). Compare com uma matriz que tenha acesso O(1)e o restante das operações O(n).

Portanto, dado um aplicativo em que inserimos, excluímos ou pesquisamos com mais frequência do que acessamos e uma escolha entre apenas essas duas estruturas, preferimos a árvore vermelha e preta. Nesse caso, você pode dizer que preferimos o O(log n)tempo de acesso mais pesado da árvore vermelha e preta .

Por quê? Porque o acesso não é nossa principal preocupação. Estamos negociando: o desempenho de nosso aplicativo é mais fortemente influenciado por outros fatores além deste. Permitimos que esse algoritmo em particular sofra desempenho porque obtemos grandes ganhos otimizando outros algoritmos.

Portanto, a resposta para sua pergunta é simplesmente a seguinte: quando a taxa de crescimento do algoritmo não é o que queremos otimizar , quando queremos otimizar outra coisa. Todas as outras respostas são casos especiais disso. Às vezes, otimizamos o tempo de execução de outras operações. Às vezes, otimizamos a memória. Às vezes, otimizamos a segurança. Às vezes, otimizamos a manutenção. Às vezes, otimizamos para o tempo de desenvolvimento. Mesmo a constante de substituição que é baixa o suficiente para importar é otimizada para o tempo de execução quando você sabe que a taxa de crescimento do algoritmo não é o maior impacto no tempo de execução. (Se o seu conjunto de dados estivesse fora desse intervalo, você otimizaria a taxa de crescimento do algoritmo, pois acabaria dominando a constante.) Tudo tem um custo e, em muitos casos, trocamos o custo de uma taxa de crescimento maior pelo algoritmo para otimizar outra coisa.

jpmc26
fonte
Não tenho certeza de como as operações que permitem que você use a matriz com O (1) e atualizem O (n) correspondem à árvore vermelha e preta, na qual as pessoas pensavam (pelo menos eu). Na maioria das vezes, eu pensava primeiro na pesquisa baseada em chaves para árvore vermelha-preta. Mas, para combinar com a matriz, deve ser uma estrutura um pouco diferente que mantenha a quantidade de subnós nos nós superiores para fornecer pesquisa baseada em índice e reindexar na inserção. Embora eu concorde que o preto-vermelho possa ser usado para manter o equilíbrio, você pode usar uma árvore equilibrada se quiser ser vago sobre os detalhes das operações correspondentes.
ony
@ony Uma árvore vermelha-preta pode ser usada para definir uma estrutura de tipo de mapa / dicionário, mas não precisa ser. Os nós podem ser apenas elementos, implementando essencialmente uma lista classificada.
Jpmc26 28/07/19
lista e matriz classificadas que definem a ordem dos elementos têm diferentes quantidades de informações. Um é baseado na ordem entre os elementos e o conjunto e outro define a sequência arbitrária que não é necessária para definir a ordem entre os elementos. Outra coisa é o que é "acesso" e "pesquisa" que você declara ser O(log n)da "árvore vermelho-preta"? A inserção da 5posição 2 da matriz [1, 2, 1, 4]resultará em [1, 2, 5, 1 4](o elemento 4obterá o índice atualizado de 3 para 4). Como você vai obter esse comportamento na O(log n)"árvore vermelho-preta" que você faz referência como "lista classificada"?
ony
@ony "lista e array ordenados que definem a ordem dos elementos têm diferentes quantidades de informações." Sim, e é por isso que eles têm características de desempenho diferentes. Você está perdendo o ponto. Um não substitui o outro em todas as situações. Eles otimizam coisas diferentes e fazem trocas diferentes , e o ponto é que os desenvolvedores estão tomando decisões sobre essas trocas constantemente.
Jpmc26 30/07/19
@ony Acessar, pesquisar, inserir e excluir têm significados específicos no contexto do desempenho do algoritmo. O acesso está buscando um elemento por posição. A pesquisa está localizando um elemento por valor (que só tem aplicação prática como verificação de contenção para uma estrutura não-mapeada). Inserir e excluir deve ser simples, no entanto. Exemplo de uso pode ser visto aqui .
Jpmc26 30/07/19
23

Sim.

Em um caso real, executamos alguns testes em pesquisas de tabela com chaves de cadeia curta e longa.

Usamos a std::map, a std::unordered_mapcom um hash que é amostrado no máximo 10 vezes ao longo do comprimento da string (nossas chaves tendem a ser como guias, portanto isso é decente) e um hash que mostra todos os caracteres (em teoria, colisões reduzidas), um vetor não classificado em que fazemos uma ==comparação e (se bem me lembro) um vetor não classificado em que também armazenamos um hash, primeiro compare o hash e depois os caracteres.

Esses algoritmos variam de O(1)(unordered_map) a O(n)(pesquisa linear).

Para N de tamanho modesto, muitas vezes o O (n) vence o O (1). Suspeitamos que isso ocorra porque os contêineres baseados em nós exigiram que nosso computador pulasse mais na memória, enquanto os contêineres lineares não.

O(lg n)existe entre os dois. Não me lembro como foi.

A diferença de desempenho não era tão grande e, em conjuntos de dados maiores, o baseado em hash teve um desempenho muito melhor. Então ficamos com o mapa não ordenado baseado em hash.

Na prática, para tamanho razoável n, O(lg n)é O(1). Se o seu computador só tiver espaço para 4 bilhões de entradas na sua tabela, então O(lg n)será delimitado acima por 32. (lg (2 ^ 32) = 32) (em ciência da computação, lg é a abreviação de log 2).

Na prática, os algoritmos lg (n) são mais lentos que os algoritmos O (1) não por causa do fator de crescimento logarítmico, mas porque a parte lg (n) geralmente significa que há um certo nível de complexidade no algoritmo, e essa complexidade adiciona um fator constante maior que qualquer um dos "crescimentos" do termo lg (n).

No entanto, algoritmos complexos O (1) (como mapeamento de hash) podem facilmente ter um fator constante semelhante ou maior.

Yakk - Adam Nevraumont
fonte
21

A possibilidade de executar um algoritmo em paralelo.

Não sei se existe um exemplo para as aulas O(log n)eO(1) , para alguns problemas, você escolhe um algoritmo com uma classe de complexidade mais alta quando o algoritmo é mais fácil de executar em paralelo.

Alguns algoritmos não podem ser paralelizados, mas possuem uma classe de complexidade tão baixa. Considere outro algoritmo que alcança o mesmo resultado e pode ser paralelo facilmente, mas possui uma classe de complexidade mais alta. Quando executado em uma máquina, o segundo algoritmo é mais lento, mas quando executado em várias máquinas, o tempo real de execução diminui e diminui, enquanto o primeiro algoritmo não pode acelerar.

Simulante
fonte
Mas tudo o que a paralelização faz é reduzir o fator constante de que outros falaram, certo?
gengkev 15/12/2015
1
Sim, mas um algoritmo paralelo pode dividir o fator constante por 2 toda vez que você duplicar o número de máquinas em execução. Outro algoritmo de thread único pode reduzir o fator constante apenas uma vez de maneira constante. Portanto, com um algoritmo paralelo, você pode reagir dinamicamente ao tamanho de n e ser mais rápido no tempo de execução do relógio de parede.
Simulant
15

Digamos que você esteja implementando uma lista negra em um sistema incorporado, em que números entre 0 e 1.000.000 possam estar na lista negra. Isso deixa duas opções possíveis:

  1. Use um conjunto de bits de 1.000.000 de bits
  2. Use uma matriz classificada dos números inteiros na lista negra e use uma pesquisa binária para acessá-los

O acesso ao conjunto de bits terá acesso constante garantido. Em termos de complexidade de tempo, é ideal. Do ponto de vista teórico e prático (é O (1) com uma sobrecarga constante extremamente baixa).

Ainda assim, você pode preferir a segunda solução. Especialmente se você espera que o número de números inteiros na lista negra seja muito pequeno, pois será mais eficiente em termos de memória.

E mesmo que você não desenvolva um sistema incorporado em que a memória seja escassa, eu apenas posso aumentar o limite arbitrário de 1.000.000 para 1.000.000.000.000 e apresentar o mesmo argumento. Então o conjunto de bits exigiria cerca de 125G de memória. Ter uma complexidade complexa garantida de O (1) pode não convencer seu chefe a fornecer um servidor tão poderoso.

Aqui, eu preferiria fortemente uma pesquisa binária (O (log n)) ou árvore binária (O (log n)) sobre o conjunto de bits O (1). E provavelmente, uma tabela de hash com sua pior complexidade de O (n) superará todos eles na prática.

Philipp Claßen
fonte
12

As pessoas já responderam à sua pergunta exata. Por isso, abordarei uma pergunta um pouco diferente na qual as pessoas podem estar pensando quando vierem para cá.

Muitos algoritmos e estruturas de dados do "O (1) tempo" na verdade levam apenas o tempo O (1) esperado , o que significa que seu tempo médio de execução é O (1), possivelmente apenas sob certas suposições.

Exemplos comuns: hashtables, expansão de "listas de matrizes" (também conhecidas como matrizes / vetores de tamanho dinâmico).

Nesses cenários, você pode preferir usar estruturas de dados ou algoritmos cujo tempo é garantido como absolutamente limitado logaritmicamente, mesmo que eles possam ter um desempenho pior, em média.
Um exemplo pode, portanto, ser uma árvore de pesquisa binária equilibrada, cujo tempo de execução é pior, em média, mas melhor no pior dos casos.

user541686
fonte
11

A questão mais geral é se existem situações em que um preferem um O(f(n))algoritmo para um O(g(n))algoritmo, embora g(n) << f(n)como ntende ao infinito. Como outros já mencionaram, a resposta é claramente "sim" no caso em que f(n) = log(n)e g(n) = 1. Às vezes é sim, mesmo no caso f(n)polinomial, mas g(n)é exponencial. Um exemplo famoso e importante é o do algoritmo Simplex para resolver problemas de programação linear. Na década de 1970, isso foi demonstrado O(2^n). Portanto, seu comportamento de pior caso é inviável. Mas - seu caso médio, comportamento é extremamente bom, mesmo para problemas práticos com dezenas de milhares de variáveis ​​e restrições. Nos anos 80, algoritmos de tempo polinomial (comoO algoritmo de ponto interior de Karmarkar) para programação linear foram descobertos, mas 30 anos depois o algoritmo simplex ainda parece ser o algoritmo de escolha (exceto para alguns problemas muito grandes). Esse é o motivo óbvio pelo qual o comportamento de casos médios geralmente é mais importante que o de casos piores, mas também por um motivo mais sutil de que o algoritmo simplex é, em certo sentido, mais informativo (por exemplo, informações de sensibilidade são mais fáceis de extrair).

John Coleman
fonte
10

Para colocar meus 2 centavos em:

Às vezes, um algoritmo de complexidade pior é selecionado no lugar de um algoritmo melhor, quando o algoritmo é executado em um determinado ambiente de hardware. Suponha que nosso algoritmo O (1) acesse de maneira não sequencial todos os elementos de uma matriz de tamanho fixo muito grande para resolver nosso problema. Em seguida, coloque essa matriz em um disco rígido mecânico ou em uma fita magnética.

Nesse caso, o algoritmo O (logn) (suponha que ele acesse o disco sequencialmente) se torna mais favorável.

uylmz
fonte
Devo acrescentar aqui que, na unidade ou fita de acesso sequencial, o algoritmo O (1) se torna O (n), razão pela qual a solução sequencial se torna mais favorável. Muitas operações O (1) dependem de que a adição e a pesquisa indexada sejam um algoritmo de tempo constante, que não está em um espaço de acesso seqüencial.
TheHansinator
9

Há um bom caso de uso para o uso de um algoritmo O (log (n)) em vez de um algoritmo O (1) que as inúmeras outras respostas ignoraram: imutabilidade. Os mapas de hash têm O (1) put e gets, assumindo uma boa distribuição dos valores de hash, mas eles exigem um estado mutável. Os mapas de árvores imutáveis ​​têm O (log (n)) put e gets, o que é assintoticamente mais lento. No entanto, a imutabilidade pode ser valiosa o suficiente para compensar o desempenho pior e, no caso em que várias versões do mapa precisam ser mantidas, a imutabilidade permite evitar a cópia do mapa, que é O (n) e, portanto, pode melhorar desempenho.

Restabelecer Monica
fonte
9

Simplesmente: porque o coeficiente - os custos associados à configuração, armazenamento e tempo de execução dessa etapa - pode ser muito, muito maior com um problema menor de grande O que com um maior. Big-O é apenas uma medida da escalabilidade dos algoritmos .

Considere o seguinte exemplo do Dicionário do Hacker, propondo um algoritmo de classificação baseado na interpretação de múltiplos mundos da mecânica quântica :

  1. Permita a matriz aleatoriamente usando um processo quântico,
  2. Se a matriz não estiver classificada, destrua o universo.
  3. Todos os universos restantes agora estão classificados [incluindo o que você está].

(Fonte: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Observe que o grande O deste algoritmo é O(n)que supera qualquer algoritmo de classificação conhecido até o momento em itens genéricos. O coeficiente da etapa linear também é muito baixo (já que é apenas uma comparação, não uma troca, que é feita linearmente). Um algoritmo semelhante poderia, de fato, ser usado para resolver qualquer problema em NP e co-NP em tempo polinomial, uma vez que cada solução possível (ou prova possível de que não há solução) pode ser gerada usando o processo quântico, e então verificada em tempo polinomial.

No entanto, na maioria dos casos, provavelmente não queremos correr o risco de que Múltiplos Mundos possam não estar corretos, sem mencionar que o ato de implementar a etapa 2 ainda é "deixado como um exercício para o leitor".

TheHansinator
fonte
7

A qualquer momento em que n é limitado e o multiplicador constante do algoritmo O (1) é maior que o limite no log (n). Por exemplo, armazenar valores em um hashset é O (1), mas pode exigir um cálculo caro de uma função de hash. Se os itens de dados puderem ser comparados trivialmente (com relação a alguma ordem) e o limite em n for tal que o log n seja significativamente menor que o cálculo de hash em qualquer item, o armazenamento em uma árvore binária balanceada poderá ser mais rápido que o armazenamento em um hashset.

Dmitry Rubanovich
fonte
6

Em uma situação em tempo real em que você precisa de um limite superior firme, você selecionaria, por exemplo, um montão de mercadorias em oposição a um Quicksort, porque o comportamento médio do montão de mercadorias também é o pior dos casos.

Marquês de Lorne
fonte
6

Adicionando às respostas já boas. Um exemplo prático seria os índices Hash e os índices da árvore B no banco de dados do postgres.

Os índices de hash formam um índice de tabela de hash para acessar os dados no disco enquanto btree, como o nome sugere, usa uma estrutura de dados Btree.

No tempo Big-O, são O (1) vs O (logN).

Atualmente, os índices de hash são desencorajados no postgres, pois em uma situação da vida real, particularmente em sistemas de banco de dados, é muito difícil obter hash sem colisão (pode levar a uma complexidade do pior caso de O (N)) e, por isso, é ainda mais difícil eles travam com segurança (chamado de gravação antecipada - WAL no postgres).

Essa troca é feita nessa situação, pois O (logN) é bom o suficiente para índices e a implementação de O (1) é bastante difícil e a diferença de horário não importa.

Madusudanan
fonte
4

Quando né pequeno e O(1)é constantemente lento.

HoboBen
fonte
3
  1. Quando a unidade de trabalho "1" em O (1) é muito alta em relação à unidade de trabalho em O (log n) e o tamanho esperado do conjunto é pequeno. Por exemplo, provavelmente é mais lento calcular códigos de hash do Dicionário do que iterar uma matriz se houver apenas dois ou três itens.

ou

  1. Quando os requisitos de memória ou outros recursos não horários no algoritmo O (1) são excepcionalmente grandes em relação ao algoritmo O (log n).
Joel Coehoorn
fonte
3
  1. ao redesenhar um programa, um procedimento é otimizado com O (1) em vez de O (lgN), mas se não é o gargalo deste programa e é difícil entender o O (1) alg. Então você não precisaria usar o algoritmo O (1)
  2. quando O (1) precisa de muita memória que você não pode fornecer, enquanto o tempo de O (lgN) pode ser aceito.
yanghaogn
fonte
1

Esse é geralmente o caso dos aplicativos de segurança que queremos projetar problemas cujos algoritmos são lentos de propósito, a fim de impedir que alguém obtenha uma resposta a um problema muito rapidamente.

Aqui estão alguns exemplos em cima da minha cabeça.

  • Às vezes, o hash de senha é arbitrariamente lento para tornar mais difícil adivinhar senhas por força bruta. Esta publicação sobre Segurança da informação tem um ponto de bala sobre ela (e muito mais).
  • Bit Coin usa um problema controlável e lento para uma rede de computadores resolver, a fim de "minerar" moedas. Isso permite que a moeda seja extraída a uma taxa controlada pelo sistema coletivo.
  • Cifras assimétricas (como o RSA ) são projetadas para decriptografar sem que as chaves sejam intencionalmente lentas, a fim de impedir que outra pessoa sem a chave privada decifre a criptografia. Os algoritmos são projetados para serem decifrados em um O(2^n)tempo que, esperançosamente, né o comprimento do bit da chave (isso é força bruta).

Em outros lugares do CS, o Quick Sort é O(n^2)o pior caso, mas no geral é O(n*log(n)). Por esse motivo, às vezes a análise "Big O" não é a única coisa com que você se preocupa ao analisar a eficiência do algoritmo.

Frank Bryce
fonte