Complexidade logarítmica versus dupla logarítmica

9

Em aplicativos do mundo real, há um benefício concreto ao usar os algoritmos vez dos \ mathcal {O} (\ log (n)) ?O ( log ( n ) )O(registro(registro(n))O(registro(n))

É o caso quando se usa, por exemplo, árvores de van Emde Boas, em vez de implementações mais convencionais de árvores de pesquisa binária. Mas, por exemplo, se pegarmos n<106 , na melhor das hipóteses, o algoritmo logarítmico duplo supera o algoritmo logarítmico por (aproximadamente) um fator de 5 . E também, em geral, a implementação é mais complicada e complexa.

Dado que eu pessoalmente prefiro o BST do que as árvores VEB, o que você acha?

Pode-se demonstrar facilmente que:

n<106. registronregistro(registro(n))<5.26146

Ghassen Hamrouni
fonte
basicamente, você deve observar as constantes envolvidas no algoritmo para obter menor valor / tamanho da entrada. Idealmente, gostaríamos que eles fossem pequenos.
singhsumit
3
Observe que houve várias melhorias desde as árvores VEB, no valor de estruturas de dados na RAM com complexidade de pesquisa / inserção / exclusão de sem randomização (determinística) e com randomização. Consulte Classificação determinística em Tempo e espaço linear. por Han e Tempo esperado e espaço linear. por Han e Thorup. O ( O(euog euog n) O (nloglogn) O (O(euog euog n)O(n euog euog n)O(euog euog n)
AT
No mundo real, um fator 5 é bastante significativo, e o número de itens geralmente pode ser 10 ^ 9 ou até 10 ^ 12.
usar o seguinte código

Respostas:

10

Não esqueça que ainda cresce exponencialmente (em ) mais rápido que !log ( n ) log ( log n )registronregistro(n)registro(registron)

De fato, se você observar o quociente de e , não há muito impressionante para ver:log ( log ( n ) )registro(n)registro(registro(n))

log (n) / log (log (n))
[ fonte ]

Mas, ainda assim, você recebe um fator de cinco a seis para tamanhos de até . Observe que tamanhos maiores não são incomuns na prática, e uma aceleração por esse fator é impressionante ! Pode fazer a diferença entre ter resultados após o almoço ou apenas amanhã. Esteja ciente de que parte da aceleração pode ser devorada por constantes mais altas da implementação da árvore; você teria que plotar (ou analisar) e com as constantes reais do tempo de execução para obter uma imagem real.100000cregistro(n)dregistro(registro(n))c,d

Além disso, o que Dave menciona é importante: se a operação acelerada for executada, digamos, linearmente, com frequência, acelerações constantes se tornam acelerações lineares, ou seja, você pode diminuir a constante principal de todo o seu algoritmo! Como eu disse acima, isso é incrível. Veja o que acontece se você executar a operação vezes:n

n * log (n) / (n * log (log (n)))
[ fonte ]

Agora, se isso não vale a pena, não sei o quê.

Rafael
fonte
6

Pode-se imaginar que a diferença de complexidade realmente não importa tanto e que o tempo de execução real é mais importante. Mas se o algoritmo estiver no centro de outro algoritmo, essa diferença poderá ser importante.

De um propósito puramente teórico, a diferença de curso é importante, especialmente se o algoritmo fizer parte de outro. Pode colocar o algoritmo maior em uma classe de complexidade diferente.

Dave Clarke
fonte
6

Na verdade, eu já comparei a árvore da van Emde-Boas uma vez. Comparei com uma árvore AA, um mapa de hash e uma matriz de bits.

Os testes executam sizeinserções com números aleatórios no intervalo [0, bound], depois sizepesquisam, sizeexcluem e depois sizepesquisam novamente . As exclusões também são feitas em números aleatórios, portanto, primeiro você precisa descobrir se elas estão na estrutura.

Aqui estão os resultados ( size= 2000000, bound= 10000000) em segundos:

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

Como você pode ver, as árvores van Emde-Boas são duas vezes mais lentas que os mapas de hash, dez vezes mais lentas que as matrizes de bits e 5 vezes mais rápidas que as árvores de pesquisa binária.

É claro que o que precede precisa de um aviso: os testes são artificiais, é possível melhorar o código ou usar um idioma diferente com um compilador cuja saída é mais rápida e assim por diante.

Essa isenção de responsabilidade está no centro do motivo pelo qual usamos a análise assintótica no design de algoritmos: como você não tem idéia do que são as constantes e como as constantes podem mudar dependendo dos fatores ambientais, o melhor que podemos fazer é uma análise assintótica.

registronregistroregistron232.registro232.=32.registro32.=5

Alex ten Brink
fonte
Talvez pule para R (ou equivalente) e produz alguns gráficos bonitos (como @Raphael fez).
22412 Dave Clarke
11
registronregistroregistron
@ DaveClarke: obrigado pelas sugestões. Infelizmente, sou muito ruim em produzir imagens bonitas - acho que minha edição melhorou a legibilidade dos meus resultados.
Alex-Brink
Provavelmente, não há dados suficientes para uma foto adequada. Não importa ... mas aprender a tirar boas fotos é uma habilidade útil.
22412 Dave Clarke