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

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?

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.

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.

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 ² <6 n ² ) . 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.

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 .

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.)

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.

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.

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.

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.

Minha resposta aqui A seleção rápida e aleatória ponderada 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 mnão é muito grande.

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.

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).

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.

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.

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".

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.

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.

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.

Quando né pequeno e O(1)é 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 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

2. 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).

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.

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.