Há algum caso em que você preferiria um algoritmo de complexidade de tempo maior em relação ao menor?

Há algum caso em que você preferiria complexidade de tempo O(log n) à complexidade de tempo O(1) ? Ou O(n) para O(log n) ?

Você tem algum exemplo?

Pode haver muitas razões para preferir um algoritmo com maior complexidade de tempo O maior que o inferior:

  • Na maioria das vezes, a complexidade menor de O grande é mais difícil de alcançar e requer implementação qualificada, muito conhecimento e muitos testes.
  • big-O oculta os detalhes sobre uma constante : o algoritmo que executa em 10^5 é melhor do ponto de vista do big-O do que 1/10^5 * log(n) ( O(1) vsO O(log(n) ) mas, para o mais razoável n o primeiro terá melhor desempenho.Por exemplo, a melhor complexidade para a multiplicação de matrizes é O(n^2.373) mas a constante é tão alta que nenhuma (em meu conhecimento) as bibliotecas computacionais a utilizam.
  • big-O faz sentido quando você calcula sobre algo grande. Se você precisar classificar uma matriz de três números, pouco importa se você usar o algoritmo O(n*log(n)) ou O(n^2) .
  • às vezes, a vantagem da complexidade de tempo das minúsculas pode ser muito insignificante. Por exemplo, existe uma tree de tango de estrutura de dados que fornece uma complexidade de tempo O(log log N) para encontrar um item, mas há também uma tree binária que encontra o mesmo em O(log n) . Mesmo para um grande número de n = 10^20 a diferença é insignificante.
  • complexidade de tempo não é tudo. Imagine um algoritmo que é executado em O(n^2) e requer memory O(n^2) . Pode ser preferível em O(n^3) tempo e O(1) espaço quando o n não é realmente grande. O problema é que você pode esperar por um longo tempo, mas duvido que você pode encontrar uma RAM grande o suficiente para usá-lo com o seu algoritmo
  • A paralelização é um bom recurso em nosso mundo distribuído. Existem algoritmos que são facilmente paralelizáveis, e alguns não paralelizam. Às vezes, faz sentido executar um algoritmo em 1000 máquinas com maior complexidade 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 que pode ser incrivelmente rápido (porque outras pessoas podem te forçar muito mais rápido)
  • embora isso não esteja relacionado à alternância de complexidade, mas algumas das funções de segurança devem ser escritas de maneira a evitar ataques de temporização . Eles geralmente permanecem na mesma class de complexidade, mas são modificados de uma forma que sempre leva pior situação para fazer alguma coisa. Um exemplo é comparar que as strings são iguais. Na maioria das aplicações, faz sentido quebrar rápido se os primeiros bytes forem diferentes, mas em segurança você ainda esperará o final para 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 ordenação por inserção, por exemplo, tem uma complexidade média de tempo de O(n^2) , pior que quicksort ou mergesort, mas como um algoritmo online pode classificar eficientemente uma lista de valores à medida que são recebidos (como input do usuário) outros algoritmos só podem operar eficientemente em uma lista completa de valores.

Há sempre a constante oculta, que pode ser menor no algoritmo O (log n ). Por isso, pode trabalhar mais rápido na prática para dados da vida real.

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

Há também preocupação com o tempo do desenvolvedor – O (log n ) pode ser 1000x mais fácil de implementar e verificar.

Estou surpreso que ninguém tenha mencionado aplicativos ligados à memory ainda.

Pode haver um algoritmo que tenha menos operações de ponto flutuante devido à sua complexidade (por exemplo, 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 estiver mais ligado à memory.

O que quero dizer com “ligado à memory” é que muitas vezes você está acessando dados que estão constantemente fora do cache. Para obter esses dados, você precisa extrair a memory do espaço de memory real para o cache antes de executar sua operação. Este passo de busca é frequentemente muito lento – muito mais lento que a sua operação.

Portanto, se seu algoritmo exigir mais operações (ainda que essas operações sejam executadas em dados que já estão em cache [e, portanto, nenhuma busca necessária]), ele ainda terá um desempenho superior ao seu algoritmo com menos operações (que deve ser executado fora de -cache dados [e, portanto, exigem uma busca]) em termos de tempo de parede real.

Em contextos onde a segurança de 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 temporização .

Alistra acertou em cheio, mas não deu nenhum exemplo, então eu irei.

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

O (log N) abordagem: você tem uma lista ordenada. 44 bytes se ASCII, 84 se Unicode. Como alternativa, trate o UPC como um int64 e você terá 42 e 72 bytes. 10.000 registros – no maior caso, você está olhando um pouco abaixo de um megabyte de armazenamento.

O (1) abordagem: Não armazene o UPC, em vez disso você o usa como uma input no array. No pior dos casos, você está vendo quase um terço de 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. Eu posso imaginar a segunda abordagem sendo a resposta certa se por algum motivo você estiver rodando em um ambiente onde a RAM é criticamente curta, mas você tem muito armazenamento em massa. Um terço de um terabyte em um disco não é grande coisa, fazer com que seus dados em um teste do disco valham alguma coisa. A abordagem binária simples leva 13 em média. (Note, no entanto, que, ao agrupar suas chaves, você pode conseguir isso com 3 leituras garantidas e, na prática, você armazenaria em cache a primeira.)

Considere uma tree vermelha e preta. Tem access, pesquisa, inserção e exclusão de O(log n) . Compare com uma matriz, que tem access de O(1) e o resto das operações são O(n) .

Assim, dada uma aplicação em que inserimos, excluímos ou pesquisamos com mais frequência do que acessamos e uma escolha entre apenas essas duas estruturas, preferimos a tree vermelho-preto. Nesse caso, você pode dizer que preferimos o tempo de access O(log n) mais pesado da tree vermelha e preta.

Por quê? Porque o access não é nossa preocupação primordial. Estamos fazendo um trade off: o desempenho de nossa aplicação é mais fortemente influenciado por outros fatores que não este. Permitimos que esse algoritmo específico sofra desempenho porque obtemos grandes ganhos otimizando outros algoritmos.

Portanto, a resposta à sua pergunta é simplesmente esta: 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 nós otimizamos para a memory. Às vezes, otimizamos a segurança. Às vezes, otimizamos a manutenção. Às vezes, otimizamos o tempo de desenvolvimento. Mesmo a constante principal sendo baixa o bastante para importar é otimizar 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 dataset estivesse fora desse intervalo, você otimizaria a taxa de crescimento do algoritmo porque acabaria dominando a constante.) Tudo tem um custo e, em muitos casos, trocamos o custo de uma taxa de crescimento mais alta para o algoritmo para otimizar outra coisa.

Sim.

Em um caso real, executamos alguns testes em fazer pesquisas de tabela com chaves de strings curtas e longas.

Usamos um std::map , um std::unordered_map com um hash que mostra no máximo 10 vezes o comprimento da string (nossas chaves tendem a ser guideadas, então isso é decente), e um hash que mostra cada caractere (em teoria, colisões reduzidas), um vetor não separado onde fazemos um == comparar, e (se bem me lembro) um vetor não separado onde também armazenamos um hash, primeiro comparamos o hash e comparamos 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ó exigiam que nosso computador pulasse mais na memory, enquanto os contêineres com base linear não o faziam.

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

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

Na prática, para um tamanho razoável n, O(lg n) é O(1) . Se o seu computador só tiver espaço para 4 bilhões de inputs em sua tabela, então O(lg n) será limitado por 32 . (lg (2 ^ 32) = 32) (em informática, lg é mão curta para log 2).

Na prática, algoritmos lg (n) são mais lentos que algoritmos O (1) não por causa do fator de crescimento logarítmico, mas porque a porção lg (n) normalmente significa que há um certo nível de complexidade para o algoritmo, e essa complexidade acrescenta um maior fator constante do que qualquer “crescimento” do termo lg (n).

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

A possibilidade de executar um algoritmo em paralelo.

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

Alguns algoritmos não podem ser paralelizados, mas têm uma class de complexidade tão baixa. Considere outro algoritmo que atinge o mesmo resultado e pode ser paralelizado facilmente, mas tem uma class 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 de execução real fica mais baixo e mais baixo, enquanto o primeiro algoritmo não pode acelerar.

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

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

O access ao bitset terá access constante garantido. Em termos de complexidade de tempo, é ótimo. Tanto do ponto de vista teórico como 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 inteiros na lista negra seja muito pequeno, pois será mais eficiente na memory.

E mesmo que você não desenvolva um sistema embarcado em que a memory é escassa, eu só posso aumentar o limite arbitrário de 1.000.000 para 1.000.000.000.000 e fazer o mesmo argumento. Em seguida, o bitset exigiria cerca de 125G de memory. Ter uma complexidade de pior caso garantida de O (1) pode não convencer seu chefe a fornecer-lhe um servidor tão poderoso.

Aqui, eu preferiria fortemente uma pesquisa binária (O (log n)) ou tree 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) irá superar todos eles na prática.

Minha resposta aqui Rápida seleção ponderada aleatória em todas as linhas de uma matriz estocástica é um exemplo em que um algoritmo com complexidade O (m) é mais rápido que um com complexidade O (log (m)), quando m não é muito grande.

As pessoas já responderam à sua pergunta exata, então vou abordar uma questão ligeiramente diferente na qual as pessoas podem estar pensando ao vir para cá.

Muitos dos algoritmos e estruturas de dados “O (1) time” na verdade tomam apenas o tempo O (1) esperado , significando que seu tempo médio de execução é O (1), possivelmente apenas sob certas suposições.

Exemplos comuns: hashtables, expansão de “listas de arrays” (também conhecidas como arrays / vetores dimensionados dinamicamente).

Nesses cenários, você pode preferir usar estruturas de dados ou algoritmos cujo tempo é garantido como sendo totalmente limitado logaritmicamente, embora eles possam ter um desempenho pior em média.
Um exemplo pode, portanto, ser uma tree de busca binária balanceada, cujo tempo de execução é pior na média, mas melhor no pior dos casos.

Uma questão mais geral é se há situações em que se preferiria um algoritmo O(f(n)) a um algoritmo O(g(n)) , embora g(n) << f(n) como n tenda ao infinito. Como outros já mencionaram, a resposta é claramente "sim" no caso em que f(n) = log(n) g(n) = 1 . Às vezes, sim, mesmo no caso em que 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, mostrou-se O(2^n) . Assim, seu pior comportamento é inviável. Mas - seu comportamento de caso médio é extremamente bom, mesmo para problemas práticos com dezenas de milhares de variables ​​e restrições. Na década de 1980, foram descobertos algoritmos de tempo polinomial (como o algoritmo de pontos interiores de Karmarkar ) para programação linear, mas 30 anos depois o algoritmo simplex ainda parece ser o algoritmo de escolha (exceto para alguns problemas muito grandes). Isso é pela razão óbvia de que o comportamento de caso médio é geralmente mais importante do que o comportamento de pior caso, mas também por um motivo mais sutil de que o algoritmo simplex é mais informativo (por exemplo, é mais fácil extrair informações de sensibilidade).

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) acessa, de forma não seqüencial, todos os elementos de uma matriz muito grande e de tamanho fixo para resolver nosso problema. Em seguida, coloque essa matriz em um disco rígido mecânico ou uma fita magnética.

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

Há um bom caso de uso para usar 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) puts e gets, assumindo uma boa distribuição dos valores de hash, mas requerem estado mutável. Mapas de trees imutáveis ​​possuem O (log (n)) puts e gets, que é assintoticamente mais lento. No entanto, a imutabilidade pode ser valiosa o suficiente para compensar o pior desempenho e no caso em que várias versões do mapa precisam ser retidas, a imutabilidade permite evitar a necessidade de copiar o mapa, que é O (n) e, portanto, pode melhorar desempenho.

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

Considere o seguinte exemplo do Dicionário do Hacker, propondo um algoritmo de ordenação baseado na Interpretação da Mecânica Quântica em Múltiplos Mundos :

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

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

Observe que o big-O deste algoritmo é O(n) , que supera qualquer algoritmo de ordenação conhecido até hoje em itens genéricos. O coeficiente do passo linear também é muito baixo (já que é apenas uma comparação, não uma troca, que é feita linearmente). Um algoritmo similar 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 possível prova de que não há solução) pode ser gerada usando o processo quântico, então verificada em tempo polinomial.

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

Em qualquer ponto, quando 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 function hash. Se os itens de dados podem ser comparados trivialmente (com relação a alguma ordem) e o limite em n é tal que log n é significativamente menor que o cálculo hash em qualquer item, então armazenar em uma tree binária balanceada pode ser mais rápido que armazenar em um hashset.

Em uma situação em tempo real em que você precisa de um limite superior firme, você selecionaria, por exemplo, um heapsort em vez de um Quicksort, porque o comportamento médio do heapsort também é seu pior comportamento.

Somando-se às já boas respostas. Um exemplo prático seria índices Hash vs índices B-tree no database postgres.

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

No Big-O time estes são O (1) vs O (logN).

Índices hash são atualmente desencorajados em postgres, já que em uma situação da vida real particularmente em sistemas de database, conseguir hash sem colisão é muito difícil (pode levar a uma complexidade O (N) pior) e, por causa disso, é ainda mais difícil de fazer eles resistem a falhas (chamado write ahead logging – WAL no postgres).

Esta troca é feita nesta situação, já que O (logN) é bom o suficiente para índices e a implementação de O (1) é bastante difícil e a diferença de tempo não seria realmente importante.

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

  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 do conjunto esperado é pequeno-ish. Por exemplo, é provavelmente mais lento computar códigos de hash do Dicionário do que iterar um array se houver apenas dois ou três itens.

ou

  1. Quando a memory ou outros requisitos de resources não temporais no algoritmo O (1) são excepcionalmente grandes em relação ao algoritmo O (log n).
  1. Ao redesenhar um programa, um procedimento é otimizado com O (1) ao invés de O (lgN), mas se não é o gargalo deste programa, e é difícil entender o O (1) alg. Então você não teria que usar o algoritmo O (1)
  2. quando O (1) precisa de muita memory que você não pode fornecer, enquanto o tempo de O (lgN) pode ser aceito.

Este é frequentemente o caso de aplicações de segurança que queremos projetar problemas cujos algoritmos são lentos de propósito, a fim de impedir alguém de obter uma resposta para um problema muito rapidamente.

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

  • O hash de senhas às vezes é feito arbitrariamente lento, a fim de tornar mais difícil adivinhar senhas por força bruta. Este post de Segurança da Informação tem um ponto de bala sobre isso (e muito mais).
  • Bit Coin usa um problema controlavelmente lento para uma rede de computadores para resolver a fim de “minerar” moedas. Isso permite que a moeda seja extraída a uma taxa controlada pelo sistema coletivo.
  • As cifras assimétricas (como o RSA ) são projetadas para fazer a descriptografia sem que as chaves sejam lentas intencionalmente para evitar que outra pessoa, sem a chave privada, decifre a criptografia. Os algoritmos são projetados para serem quebrados em tempo O(2^n) onde n é o comprimento de bits da chave (isso é força bruta).

Em outro lugar no CS, Quick Sort é O(n^2) no pior caso, mas no caso geral é O(n*log(n)) . Por esse motivo, a análise “Big O” às vezes não é a única coisa que importa quando se analisa a eficiência do algoritmo.