No se puede deducir una tabla sobre la efectividad de los algoritmos

Question

No estoy completamente seguro acerca de siguiente tabla

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

La tabla proporciona el tamaño del problema que puede resolverse en el límite de tiempo dado en la columna de la izquierda cuando la complejidad algorítmica es del tamaño dado.

Estoy interesado en la deducción de la tabla.

La tabla me sugiere que

• O (n) = 10M en un segundo (Esto parece ser el poder de las computadoras actuales)
• n es el número de elementos para procesar # ¡Gracias a Guffa!

No estoy seguro de cómo se han deducido los valores en la columna de O (n * log (n)).

1. ¿Cómo puede deducir el valor 0.5M para O (n * log (n)) o 3000 para O (n ^ 2)?

Answer 1

Creo que esta tabla proporciona una ilustración muy aproximada de cuán grande puede ser n para diferentes tipos de complejidades cuando tiene un tiempo fijo (1 segundo, 1 minuto, 1 hora, 1 día o 1 año) a su disposición.

Por ejemplo 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 puede ver, el número son aproximaciones muy aproximadas. Parece que el autor ha querido usar buenos números redondos para ilustrar su punto.

Answer 2

No, n no es la cantidad de segundos, es la cantidad de elementos a procesar.

O (n) significa que el tiempo para procesar los elementos es lineal con respecto al número de elementos.

O (n & # 178;) significa que el tiempo para procesar los ítems es relativo al cuadrado del número de ítems. Si duplica el número de elementos, el tiempo de procesamiento será cuatro veces más largo.

Ver: notación O grande

La tabla supone que hay una cantidad fija de trabajo por elemento, aunque la notación O grande solo especifica cómo reacciona un algoritmo a un cambio en el número de elementos, no le dice nada acerca de cuánto trabajo hay por artículo.

Editar:
Los valores a lo largo del eje x de la tabla son solo aproximaciones basadas en el supuesto de que el trabajo por elemento es el mismo. Por ejemplo, el valor 3000 para O (n & # 178;) se redondea desde la raíz cuadrada de 10 millones, que es ~ 3162.28. La raíz cúbica de 10 millones no es 200, es ~ 215.44.

En una situación real, dos algoritmos rara vez realizan la misma cantidad de trabajo por elemento. Un algoritmo con O (log n) generalmente hace más trabajo por elemento que un algoritmo O (n) para el mismo propósito, pero aún es preferible en la mayoría de las situaciones porque se escala mucho mejor.

Answer 3

si puede hacer 10,000,000 operaciones por segundo, entonces cuando configure n = 500,000 y calcule n * log (n) = 500,000 * log2 (500,000) = 500,000 * 18 = 9,000,000 operaciones que es aproximadamente 10,000,000 para los propósitos de " segundos " clasificación.

Del mismo modo, con n = 3,000 obtienes n ^ 2 = 9,000,000. Entonces, en cada línea, el número de operaciones es aproximadamente el mismo.