Algoritmos do mundo real que superam em grande escala na classe abaixo existem? [fechadas]

39

Ontem à noite eu estava discutindo com outro programador que, embora algo possa ser O (1), uma operação que é O (n) pode superá-lo se houver uma grande constante no algoritmo O (1). Ele discordou, então eu trouxe aqui.

Existem exemplos de algoritmos que superam em muito os da classe abaixo? Por exemplo, O (n) sendo mais rápido que O (1) ou O (n 2 ) sendo mais rápido que O (n).

Matematicamente, isso pode ser demonstrado para uma função com limites superiores assintóticos, quando você desconsidera fatores constantes, mas esses algoritmos existem na natureza? E onde eu encontraria exemplos deles? Para quais tipos de situações eles são usados?

    
por KyleWpppd 07.10.2011 / 19:31
fonte

20 respostas

44

Pesquisas em tabelas de dados fixas muito pequenas. Uma tabela de hash otimizada pode ser O (1) e ainda mais lenta que uma pesquisa binária ou até mesmo uma busca linear devido ao custo do cálculo de hash.

    
por 07.10.2011 / 01:48
fonte
24

Um exemplo simples é a diferença entre vários algoritmos de ordenação. Mergesort, Heapsort e alguns outros são O (n log n) . O Quicksort é O (n ^ 2) o pior caso. Mas muitas vezes o Quicksort é mais rápido e, na verdade, ele funciona em média como O (n log n) . Mais informações .

Outro exemplo é a geração de um único número de Fibonacci. O algoritmo iterativo é O (n) , enquanto o algoritmo baseado em matriz é O (log n) . Ainda assim, para os primeiros dois mil números de Fibonacci, o algoritmo iterativo é provavelmente mais rápido. Isso também depende da implementação do curso!

Algoritmos com melhor desempenho assintótico podem conter operações dispendiosas que não são necessárias com um algoritmo com desempenho pior, mas operações mais simples. No final, a notação O apenas nos diz algo sobre desempenho quando o argumento em que opera aumenta dramaticamente (se aproxima do infinito).

    
por 07.10.2011 / 01:41
fonte
24

Multiplicação de matrizes. O algoritmo ingênuo O (n ^ 3) é freqüentemente usado na prática como mais rápido que o O de Strassen (n ^ 2.8) para matrizes pequenas; e Strassen é usado em vez do algoritmo O (n ^ 2.3) Coppersmith – Winograd para matrizes maiores.

    
por 07.10.2011 / 12:00
fonte
18

Nota: Por favor, leia os comentários por @ back2dos abaixo e outros gurus, pois eles são de fato mais úteis do que os que escrevi - Obrigado por todos os colaboradores.

Acho que no gráfico abaixo (tirado de: Big O notation , procure por "The Pessimistic Nature of Algorithms:"), você pode ver que O (log n) não é sempre melhor que dizer O (n). Então, eu acho que seu argumento é válido.

    
por 07.10.2011 / 20:14
fonte
11

Para valores práticos de n , sim. Isso surge muito na teoria do CS. Muitas vezes, há um algoritmo complicado que apresenta um desempenho tecnicamente melhor, mas os fatores constantes são tão grandes que o tornam impraticável.

Uma vez eu tive meu professor de geometria computacional descrevendo um algoritmo para triangular um polígono em tempo linear, mas ele terminou com "muito complicado. Eu não acho que alguém realmente o implementou" (!!).

Além disso, os heaps fibonacci têm características melhores do que os heaps normais, mas não são muito populares porque não têm um desempenho tão bom na prática como pilhas regulares. Isso pode fazer cascata para outros algoritmos que usam heaps - por exemplo, os caminhos mais curtos de Dijkstra são matematicamente mais rápidos com um heap de fibonacci, mas geralmente não na prática.

    
por 23.05.2017 / 14:40
fonte
10

Compare a inserção em uma lista vinculada e a inserção em uma matriz redimensionável.

A quantidade de dados tem que ser razoavelmente grande para a inserção da lista ligada O (1) valer a pena.

Uma lista vinculada tem sobrecarga extra para os próximos ponteiros e desreferências. Um array redimensionável precisa copiar os dados. Essa cópia é O (n), mas na prática é muito rápida.

    
por 07.10.2011 / 02:35
fonte
8

A notação Big-Oh é usada para descrever a taxa de crescimento de uma função, então é possível que um algoritmo O (1) seja mais rápido, mas apenas até um certo ponto (o fator constante).

Notações comuns:

O (1) - O número de iterações (às vezes você pode se referir a isso como tempo de usuário gasto pela função) não depende do tamanho da entrada e é de fato constante.

O (n) - O número de iterações cresce em uma proporção linear para o tamanho da entrada. Significado - se o algoritmo iterar através de qualquer entrada N, 2 * N vezes, ainda é considerado O (n).

O (n ^ 2) (quadrático) - O número de iterações é o tamanho de entrada ao quadrado.

    
por 07.10.2011 / 01:48
fonte
6

Geralmente, as bibliotecas Regex são implementadas para fazer o backtracking, que tem um tempo exponencial de pior caso, em vez da geração do DFA, que tem uma complexidade de O(nm) .

O retrocesso ingênuo pode ser um melhor desempenho quando a entrada permanece no caminho rápido ou falha sem a necessidade de retroceder excessivamente.

(Embora essa decisão não seja apenas baseada em desempenho, é também permitir referências posteriores.)

    
por 07.10.2011 / 14:46
fonte
5

Algoritmo O(1) :

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Algoritmo O(n) :

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Claramente, para qualquer valor de n onde n < one_million , o algoritmo O(n) fornecido no exemplo será mais rápido do que o algoritmo O(1) .

Embora este exemplo seja um pouco facetado, é equivalente em espírito ao seguinte exemplo:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Você deve conhecer as constantes e coeficientes em sua expressão O , e deve conhecer o intervalo esperado de n , para determinar a priori qual algoritmo vai acabar sendo mais rápido.

Caso contrário, você deve comparar os dois algoritmos com valores de n no intervalo esperado para determinar a posteriori qual algoritmo acabou sendo mais rápido.

    
por 07.10.2011 / 13:50
fonte
4

Classificação:

A ordenação por inserção é O (n ^ 2), mas supera outros algoritmos de ordenação O (n * log (n)) para um pequeno número de elementos.

Esta é a razão pela qual a maioria das implementações de classificação usa uma combinação de dois algoritmos. Por exemplo. use merge sort para dividir grandes arrays até que eles atinjam um array de determinado tamanho, então use a inserção de ordenação para ordenar as unidades menores e mesclá-las novamente com o merge sort.

Veja Timsort a implementação padrão atual da classificação em Python e Java 7 que usa essa técnica.

    
por 07.10.2011 / 09:47
fonte
4

O algoritmo unificação usado na prática é exponencial no pior dos casos, para alguns dados patológicos.

Existe um algoritmo de unificação polinomial , mas é muito lento prática.

    
por 07.10.2011 / 13:19
fonte
3

O Bubblesort na memória pode superar o quicksort quando o programa está sendo trocado para o disco ou precisa ler cada item do disco ao comparar.

Este deve ser um exemplo ao qual ele pode se relacionar.

    
por 07.10.2011 / 11:33
fonte
3

Geralmente, os algoritmos mais avançados pressupõem uma certa configuração (cara). Se você precisar executá-lo apenas uma vez, talvez seja melhor usar o método de força bruta.

Por exemplo: pesquisa binária e pesquisa de tabela de hash são muito mais rápidas por pesquisa do que uma pesquisa linear, mas eles exigem que você classifique a lista ou construa a tabela de hash, respectivamente.

O tipo custará N log (N) e a tabela de hash custará pelo menos N. Agora, se você estiver fazendo centenas ou milhares de pesquisas, isso ainda é uma economia amortizada. Mas se você precisar fazer apenas uma ou duas pesquisas, talvez faça sentido apenas fazer a pesquisa linear e economizar o custo de inicialização.

    
por 18.04.2012 / 16:48
fonte
1

A descriptografia é geralmente 0 (1). Por exemplo, o espaço da chave para DES é 2 ^ 56, então a decriptografia de qualquer mensagem é uma operação de tempo constante. É só que você tem um fator de 2 ^ 56 lá, então é uma constante muito grande.

    
por 07.10.2011 / 10:05
fonte
1

Diferentes implementações de conjuntos vêm à minha mente. Um dos mais ingênuos é implementá-lo sobre um vetor, o que significa remove , bem como contains e, portanto, também add , todos tomam O (N).
Uma alternativa é implementá-lo em algum hash de propósito geral, que mapeia hashes de entrada para valores de entrada. Essa implementação de conjunto é executada com O (1) para add , contains e remove .

Se assumirmos que N é cerca de 10 ou mais, então a primeira implementação é provavelmente mais rápida. Tudo o que tem que fazer para encontrar um elemento é comparar 10 valores a um.
A outra implementação terá que iniciar todos os tipos de transformações inteligentes, que podem ser muito mais caras, do que fazer 10 comparações. Com toda a sobrecarga, você pode até ter falhas de cache e, então, não importa o quão rápido sua solução seja na teoria.

Isso não significa que a pior implementação que você possa imaginar superará a melhor, se N for pequena o suficiente. Simplesmente significa N suficientemente pequeno para que uma implementação ingênua, com baixo footprint e overhead, possa realmente exigir menos instruções e causar menos falhas de cache do que uma implementação que coloque a escalabilidade primeiro e, portanto, seja mais rápida.

Você não pode realmente saber o quão rápido tudo está em um cenário do mundo real, até você colocá-lo em um e simplesmente medi-lo. Muitas vezes os resultados são surpreendentes (pelo menos para mim).

    
por 07.10.2011 / 11:43
fonte
1

Sim, para N adequadamente adequado. Sempre haverá um N, acima do qual você sempre terá o pedido O (1) < O (Ig N) < O (N) < O (N log N) < O (N ^ c) < O (c ^ N) (onde O (1) < O (lg N) significa que em um algoritmo O (1) tomará menos operações quando N for adequadamente grande e c for uma constante fixa maior que 1) .

Digamos que um algoritmo O (1) específico tenha operações exatamente f (N) = 10 ^ 100 (um googol) e um algoritmo O (N) faça exatamente operações g (N) = 2 N + 5. O algoritmo O (N) fornecerá maior desempenho até que N seja aproximadamente um googol (na verdade, quando N > (10 ^ 100 - 5) / 2), portanto, se você espera que N esteja na faixa de 1.000 a um bilhão você sofreria uma penalidade maior usando o algoritmo O (1).

Ou para uma comparação realista, digamos que você esteja multiplicando números de n dígitos juntos. O algoritmo Karatsuba é no máximo 3 n ^ (lg 3) operações (aproximadamente O (n ^ 1.585)) enquanto o algoritmo de Schönhage-Strassen é O (N log N log log N) que é um ordem mais rápida , mas para citar a wikipedia:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^2^15 to 2^2^17 (10,000 to 40,000 decimal digits).[4][5][6]

Portanto, se você está multiplicando números de 500 dígitos, não faz sentido usar o algoritmo que é "mais rápido" por grandes argumentos O.

EDIT: Você pode encontrar f (N) em comparação com g (N), tomando o limite N- > infinito de f (N) / g (N). Se o limite for 0, então f (N) < g (N), se o limite for infinito, então f (N) > g (N), e se o limite for alguma outra constante, então f (N) ~ g (N) em termos de grande notação de O.

    
por 07.10.2011 / 20:03
fonte
1

O método simplex para programação linear pode ser exponencial no pior dos casos, enquanto algoritmos de ponto interior relativamente novos podem ser polinomiais .

No entanto, na prática, o pior caso exponencial para o método simplex não aparece - o método simplex é rápido e confiável, enquanto algoritmos iniciais de ponto interior eram lentos demais para serem competitivos. (Existem agora algoritmos de pontos interiores mais modernos que são competitivos - mas o método simplex também é ...)

    
por 18.04.2012 / 22:49
fonte
0

O algoritmo de Ukkonen para construir tentativas de sufixo é O (n log n). Tem a vantagem de estar "on-line" - ou seja, você pode adicionar mais texto de forma incremental.

Recentemente, outros algoritmos mais complexos afirmaram ser mais rápidos na prática, principalmente porque o acesso à memória deles tem maior localidade, melhorando assim a utilização do cache do processador e evitando paralisações do pipeline da CPU. Veja, por exemplo, this pesquisa , que afirma que 70 a 80% do tempo de processamento é gasto esperando pela memória e este documento descrevendo o algoritmo" wotd ".

Tentativas de sufixos são importantes na genética (para a correspondência de seqüências de genes) e, de maneira um pouco menos importante, na implementação de dicionários de Scrabble.

    
por 07.10.2011 / 19:57
fonte
0

Existe sempre o algoritmo mais rápido e mais curto para qualquer problema bem definido . É puramente teoricamente o algoritmo (assintoticamente) mais rápido.

Dada qualquer descrição de um problema P e uma instância para esse problema I , ele enumera todos os algoritmos possíveis A e provas Pr , verificando cada par se o Pr é uma prova válida de que A é o algoritmo assintoticamente mais rápido para P . Se encontrar essa prova, ela executa A em I .

A procura por esse par problemático tem complexidade O (1) (para um problema fixo P ), portanto, você sempre usa o algoritmo assintoticamente mais rápido para o problema. No entanto, como essa constante é tão inexprimivelmente enorme em quase todos os casos, esse método é completamente inútil na prática.

    
por 07.10.2011 / 20:25
fonte
0

Muitas linguagens / frameworks usam correspondência de padrões ingênuos para combinar strings em vez de KMP . Procuramos cordas como Tom, Nova York, em vez de ababaababababababababababab.

    
por 07.10.2011 / 20:53
fonte