Esta questão é em relação ao algoritmo Fisher-Yates para retornar um shuffle aleatório de uma determinada matriz. A página da Wikipedia diz que sua complexidade é O (n), mas acho que é O (n log n).
Em cada iteração i, um número inteiro aleatório é escolhido entre 1 e i. Simplesmente escrever o número inteiro na memória é O (log i) e, como não há iterações, o total é
O (log 1) + O (log 2) + ... + O (log n) = O (n log n)
o que não é melhor do que o algoritmo ingênuo. Estou faltando alguma coisa aqui?
Nota: O algoritmo ingênuo é atribuir a cada elemento um número aleatório no intervalo (0,1) e, em seguida, classificar a matriz em relação aos números atribuídos.
ds.algorithms
permutations
Tomer Vromen
fonte
fonte
O modelo padrão de computação assume que operações aritméticas em números inteiros de O (log n) bits podem ser executadas em tempo constante, uma vez que essas operações geralmente são entregues em hardware. Portanto, no algoritmo Fisher-Yates, "escrever o número inteiro i na memória" leva apenas tempo O (1).
Obviamente, é perfeitamente significativo analisar o algoritmo em termos de operações de bits, mas o modelo de custo de bits é menos preditivo do comportamento real. Até o loop simples
for i = 1 to n: print(i)requer operações de O (n log n) bit.fonte
Esta é uma resposta para "[O algoritmo de Fisher-Yates] não é melhor que o ingênuo. Estou perdendo alguma coisa aqui?" que você fez na pergunta.
No seu algoritmo "ingênuo", que usa números reais: quantos bits de precisão você usa? Se você está contando a complexidade de bits (como parece estar fazendo para Fisher-Yates) e o algoritmo usa k bits aleatórios para os números reais, então o tempo de execução seria Ω (kn log n), pois comparando dois k- números reais de bits levam tempo Ω (k). Mas k precisa ser pelo menos Ω (log n) para impedir que dois elementos sejam mapeados para o mesmo número real, o que significa que o algoritmo leva Ω (n log 2 n) tempo, que é mais lento que o embaralhamento de Fisher-Yates por um fator de log
Se você está apenas contando o número de operações aritméticas e de comparação e ignorando sua complexidade de bits, Fisher-Yates é Θ (n) e seu algoritmo é Θ (n log n), ainda um fator de log n distante.
fonte
Não há nada especial sobre números inteiros para esse problema.
Por exemplo, as tabelas de hash (armazenando qualquer tipo de valor) não têm tempo O (1) para acessar se a função de hash precisar ler todo o valor para calcular seu hash. n elementos únicos requerem log n bits, em média, para representar, não importa quão inteligente seja sua representação, e qualquer função hash que leia toda a sua entrada levará, portanto, pelo menos o tempo necessário para a computação. Na prática, eles são mais rápidos do que as árvores vermelho-escuras, mas assintoticamente não são melhores.
O brouhaha referenciado por randomwalker foi sobre um artigo do POPL 2008 ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), discutido aqui: http://blog.computationalcomplexity.org/2009/05/shaving- logs-with-unit-cost.html
Nesse post, Lance Fortnow descreve como, quando estudante, ele reclamou que a classificação realmente requer n log ^ 2 n tempo, se precisamos ler todos os bits de log n de dois elementos para compará-los, o que parece uma objeção razoável.
fonte
Na verdade, O (n log n) é um limite inferior para esse problema nos modelos em que a classificação é O (n log n). Se todas as permutações são igualmente prováveis, então o algoritmo como uma função de fluxos aleatórios a permutações deve ser subjetivo. Existem n! permutações, portanto, em algo como um modelo de árvore de decisão, existem ramos de comprimento pelo menos O (log n!) = O (n log n).
fonte
No TCS, consideramos - se não declarado de outra forma explícita - a complexidade em uma Máquina de Turing. Embora isso seja bom para propósitos teóricos, os resultados não são muito úteis na prática, pois implementamos diferentes modelos de máquinas (ou seja, aproximações finitas) no hardware. Portanto, é uma questão viável pedir complexidade nesses modelos. Por exemplo, normalmente assumimos que máquinas de registro (semelhantes a CPUs reais) podem executar operações atômicas em dois registros em tempo constante - é isso que pode ter sido empregado aqui.
Em resumo: você pensa em termos de TMs, os autores do artigo em termos de RMs. Vocês dois estão certos.
fonte