Incapaz de deduzir uma mesa sobre a eficácia dos algoritmos

Question

Eu não estou completamente certo sobre o tabela seguinte

alt texto http://files.getdropbox.com/u/175564/algTranslation .png

A tabela proporciona o tamanho do problema que pode ser resolvido no limite de tempo dada na coluna do lado esquerdo quando a complexidade algorítmica é do tamanho indicado.

Estou interessado na dedução da tabela.

A tabela sugere me que

• O (n) = 10M em um segundo (Este parece ser o poder dos computadores atuais)
• n é o número de itens para processo de # Graças ao Guffa!

Eu não sei como os valores na coluna de O (n * log (n)) foram deduzidas.

1. Como você pode deduzir o valor 0,5 M O (n * log (n)) ou 3000 para O (n ^ 2)?

Answer 1

Eu acho que esta tabela dá ilustração simplesmente alguns muito aproximada quão grande n pode ser para diferentes tipos de complexidades quando tiver fixos de tempo (1 segundo, 1 minuto, 1 hora, 1 dia ou 1 ano) à sua disposição.

Por exemplo O (n ^ 3):

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

Como você pode ver, o número é muito aproximações. Parece que o autor quis usar bons números redondos para ilustrar o seu ponto.

Answer 2

Não, n não é o número de segundos, é o número de itens para processo.

O (n) significa que o tempo para processar os itens é linear com o número de itens.

O (n²) significa que o tempo para proess os itens é relativo ao quadrado do número de itens. Se você dobrar o número de itens, o tempo de processamento será quatro vezes mais tempo.

Veja: Big O notação

A tabela assume que há uma quantidade fixa de trabalho por item, embora a notação O grande única especifica como uma algoritmo reage a uma mudança no número de itens, ele não dizer nada sobre o quanto o trabalho não é por item.

Edit:
Os valores ao longo do eixo x da tabela são apenas aproximações baseadas no pressuposto de que o trabalho por item é o mesmo. Por exemplo o valor de 3.000 para O (N²) é arredondada a partir da raiz quadrada de 10 milhões de pessoas, que é ~ 3162,28. A raiz cúbica de 10 milhões não é 200, que é ~ 215,44.

Em um situatuon real, dois algoritmos raramente fazer a mesma quantidade de trabalho por item. Um algoritmo com O (log n) normalmente faz mais trabalho por item do que um algoritmo O (n) para o mesmo fim, mas ainda assim é preferível na maioria das situações porque escalas muito melhor.

Answer 3

Se você pode fazer 10.000.000 ops por segundo, em seguida, quando você definir n = 500.000 e calcular n * log (n) = 500.000 * log2 (500.000) = 500.000 * 18 = 9.000.000 ops que é aproximadamente 10.000.000 para efeitos do "segundos" de classificação.

Da mesma forma, com n = 3.000 você começa n ^ 2 = 9.000.000. Então, em cada linha o número de operações é praticamente o mesmo.