performance - top - O(log N)== O(1)-¿Por qué no?

ggplot2 tutorial (23)

Cada vez que considero algoritmos / estructuras de datos, tiendo a reemplazar las partes de registro (N) por constantes. Oh, sé que el registro (N) diverge, pero ¿importa en las aplicaciones del mundo real?

log (infinito) <100 para todos los propósitos prácticos.

Tengo mucha curiosidad por los ejemplos del mundo real donde esto no se sostiene.

Para aclarar:

Entiendo O (f (N))
Tengo curiosidad acerca de ejemplos del mundo real donde el comportamiento asintótico importa más que las constantes del desempeño real.
Si log (N) puede ser reemplazado por una constante, puede ser reemplazado por una constante en O (N log N).

Esta pregunta es por (a) entretenimiento y (b) para reunir argumentos para usar si corro (nuevamente) en una controversia sobre el rendimiento de un diseño.

¿A qué te refieres con si "importa" o no?

Si te enfrentas a la elección de un algoritmo O(1) y un O(lg n) uno, entonces no debes asumir que son iguales. Debe elegir uno de tiempo constante. ¿Por qué no?

Y si no existe un algoritmo de tiempo constante, entonces el tiempo logarítmico es generalmente lo mejor que puede obtener. Nuevamente, ¿entonces importa ? Solo tienes que tomar el más rápido que puedas encontrar.

¿Puedes darme una situación en la que ganarías algo definiendo los dos como iguales? En el mejor de los casos, no haría ninguna diferencia, y en el peor, escondería algunas características reales de escalabilidad. Como generalmente, un algoritmo de tiempo constante será más rápido que uno logarítmico.

Incluso si, como dices, lg(n) < 100 para todos los propósitos prácticos, ese sigue siendo un factor 100 encima de tu otra sobrecarga. Si llamo a su función, N veces, entonces comienza a importar si su función ejecuta el tiempo logarítmico o constante, porque la complejidad total es entonces O(n lg n) u O(n) .

Entonces, en lugar de preguntar si "es importante" que usted suponga que la complejidad logarítmica es constante en "el mundo real", le preguntaría si tiene sentido hacerlo.

A menudo puede suponer que los algoritmos logarítmicos son lo suficientemente rápidos , pero ¿qué gana al considerarlos constantes?

Big-OH te dice que un algoritmo es más rápido que otro dado un factor constante. Si su entrada implica un factor constante lo suficientemente pequeño, puede ver grandes ganancias de rendimiento yendo con una búsqueda lineal en lugar de una búsqueda de registro (n) de alguna base.

Como han señalado otros, Big-O le explica cómo se escala el rendimiento de su problema. Confía en mí, importa. Me he encontrado varias veces con algoritmos que eran simplemente terribles y que no satisfacían las demandas de los clientes porque eran demasiado lentos. Comprender la diferencia y encontrar una solución O (1) es muchas veces una gran mejora.

Sin embargo, esa no es toda la historia, por ejemplo, puede observar que los algoritmos de la solución rápida siempre cambiarán a la ordenación de inserción para elementos pequeños (Wikipedia dice 8 - 20) debido al comportamiento de ambos algoritmos en conjuntos de datos pequeños.

Por lo tanto, se trata de entender qué compensaciones va a hacer, lo que implica una comprensión profunda del problema, la arquitectura y la experiencia para comprender qué usar y cómo ajustar las constantes involucradas.

Nadie dice que O (1) siempre es mejor que O (log N). Sin embargo, puedo garantizarle que un algoritmo O (1) también se escalará mucho mejor, por lo que incluso si hace suposiciones incorrectas sobre cuántos usuarios habrá en el sistema o el tamaño de los datos a procesar, no importará al algoritmo.

Como muchos ya han dicho, para el mundo real, primero debe considerar los factores constantes, incluso antes de preocuparse por los factores de O (log N).

Luego, considere lo que esperará que sea N. Si tiene buenas razones para pensar que N <10, puede usar una búsqueda lineal en lugar de una binaria. Eso es O (N) en lugar de O (log N), que según tus luces sería significativo, pero una búsqueda lineal que mueva los elementos encontrados al frente puede superar a un árbol balanceado más complicado, dependiendo de la aplicación .

Por otro lado, tenga en cuenta que, incluso si log N no excede 50, un factor de rendimiento de 10 es realmente enorme: si está obligado a calcular, un factor como ese puede hacer o deshacer fácilmente su aplicación. Si eso no es suficiente para ti, con frecuencia verás factores de (log N) ^ 2 o (logN) ^ 3 en los algoritmos, por lo que incluso si crees que puedes ignorar un factor de (log N), eso no significa puedes ignorar más de ellos.

Finalmente, tenga en cuenta que el algoritmo simplex para la programación lineal tiene el peor rendimiento de O (2 ^ n). Sin embargo, para problemas prácticos, el peor caso nunca aparece; en la práctica, el algoritmo simplex es rápido, relativamente simple y, en consecuencia, muy popular.

Hace unos 30 años, alguien desarrolló un algoritmo de tiempo polinomial para la programación lineal, pero inicialmente no era práctico porque el resultado era demasiado lento .

En la actualidad, existen algoritmos alternativos prácticos para la programación lineal (con wost-case de tiempo polinomial, por lo que vale), que pueden superar en la práctica el método símplex. Pero, según el problema, el método símplex sigue siendo competitivo.

Creo que este es un enfoque pragmático; O (logN) nunca será más de 64. En la práctica, siempre que los términos sean tan pequeños como O (logN), debe medir para ver si los factores constantes ganan. Ver también

¿Usos de la función de Ackermann?

Para citarme de los comentarios sobre otra respuesta:

[Big-Oh] ''Análisis'' solo importa para factores que son al menos O (N). Para cualquier factor menor, el análisis de Big-oh es inútil y debes medir.

"Con O (logN) su tamaño de entrada sí importa". Este es el punto central de la pregunta. Por supuesto que importa ... en teoría . La pregunta que hace el OP es: ¿Importa en la práctica ? Yo sostengo que la respuesta es no, no hay, y nunca habrá, un conjunto de datos para el cual el logN crecerá tan rápido como para ser siempre superado por un algoritmo de tiempo constante. Incluso para el mayor conjunto de datos prácticos imaginables en la vida de nuestros nietos, un algoritmo logN tiene una buena probabilidad de superar un algoritmo de tiempo constante: siempre debe medir.

EDITAR

Una buena charla

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

aproximadamente a la mitad, Rich discute los intentos de hash de Clojure, que son claramente O (logN), pero la base del logaritmo es grande y, por lo tanto, la profundidad del trie es como máximo 6, incluso si contiene 4 mil millones de valores. Aquí "6" sigue siendo un valor O (logN), pero es un valor increíblemente pequeño, por lo que la elección de descartar esta impresionante estructura de datos porque "Realmente necesito O (1)" es una tontería. Esto enfatiza cómo la mayoría de las otras respuestas a esta pregunta son simplemente incorrectas desde la perspectiva del pragmático que quiere que su algoritmo "corra rápido" y "escale bien", independientemente de lo que diga la "teoría".

EDITAR

Ver también

http://queue.acm.org/detail.cfm?id=1814327

que dice

¿De qué sirve un algoritmo O (log2 (n)) si esas operaciones causan fallas de página y operaciones lentas de disco? Para la mayoría de los conjuntos de datos relevantes, un algoritmo O (n) o incluso un O (n ^ 2), que evita fallas de página, correrá círculos alrededor de él.

(pero ve a leer el artículo para el contexto).

El título de la pregunta es engañoso (bien elegido para fomentar el debate, fíjate).

O (log N) == O (1) es obviamente incorrecto (y el póster es consciente de esto). La notación de Big O, por definición, se refiere al análisis asintótico. Cuando ve O (N), se toma N para acercarse al infinito. Si a N se le asigna una constante, no es Big O.

Tenga en cuenta que esto no es solo un detalle minucioso que solo los científicos informáticos teóricos deben preocuparse. Toda la aritmética utilizada para determinar la función O para un algoritmo se basa en ella. Cuando publica la función O para su algoritmo, es posible que esté omitiendo mucha información sobre su rendimiento.

El análisis de Big O es genial, porque le permite comparar algoritmos sin atascarse en problemas específicos de la plataforma (tamaños de palabra, instrucciones por operación, velocidad de memoria versus velocidad de disco). Cuando N va al infinito, esos problemas desaparecen. Pero cuando N es 10000, 1000, 100, esos problemas, junto con todas las otras constantes que dejamos fuera de la función O, comienzan a importar.

Para responder la pregunta del cartel: O (log N)! = O (1), y tiene razón, los algoritmos con O (1) a veces no son mucho mejores que los algoritmos con O (log N), dependiendo del tamaño de la entrada, y todas esas constantes internas que se omitieron durante el análisis Big O.

Si sabe que va a aumentar N, utilice el análisis Big O. Si no lo eres, entonces necesitarás algunas pruebas empíricas.

Es posible que le interese Soft-O, que ignora el costo logarítmico. Verifique este párrafo en Wikipedia.

Este es un error común: recuerde que la notación Big O NO le informa sobre el rendimiento absoluto de un algoritmo con un valor dado, simplemente le indica el comportamiento de un algoritmo a medida que aumenta el tamaño de la entrada.

Cuando lo tomas en ese contexto, queda claro por qué un algoritmo A ~ O (logN) y un algoritmo B ~ O (1) son diferentes:

si ejecuto A en una entrada de tamaño a, entonces en una entrada de tamaño 1000000 * a, puedo esperar que la segunda entrada tome registro (1,000,000) veces, siempre y cuando la primera entrada

si ejecuto B en una entrada de tamaño a, entonces en una entrada de tamaño 1000000 * a, puedo esperar que la segunda entrada tome aproximadamente la misma cantidad de tiempo que la primera entrada

EDITAR : Pensando en su pregunta un poco más, creo que hay algo de sabiduría en ella. Aunque nunca diría que es correcto decir O (lgN) == O (1), ES POSIBLE que un algoritmo O (lgN) pueda usarse sobre un algoritmo O (1). Esto se retrotrae al punto sobre el rendimiento absoluto anterior: el simple hecho de saber que un algoritmo es O (1) y otro algoritmo es O (lgN) NO es suficiente para declarar que debe usar el O (1) sobre el O (lgN), ciertamente posible, dado su rango de posibles entradas, una O (lgN) podría servirle mejor.

La igualdad, la forma en que la describes, es un abuso común de la notación.

Para aclarar: usualmente escribimos f (x) = O (logN) para implicar que "f (x) es O (logN)".

En cualquier caso, O(1) significa un número constante de pasos / tiempo (como un límite superior) para realizar una acción independientemente de qué tan grande sea el conjunto de entrada. Pero para O(logN) , el número de pasos / tiempo sigue creciendo como una función del tamaño de entrada (el logaritmo del mismo), simplemente crece muy lentamente. Para la mayoría de las aplicaciones del mundo real, puede estar seguro al asumir que este número de pasos no excederá los 100, sin embargo, apuesto a que hay múltiples ejemplos de conjuntos de datos lo suficientemente grandes como para marcar su declaración como peligrosa y vacía (rastros de paquetes, mediciones ambientales y mucho mas).

La notación Big O le informa sobre cómo cambia su algoritmo a medida que crece la información. O (1) te dice que no importa cuánto crezca tu entrada, el algoritmo siempre será igual de rápido. O (logn) dice que el algoritmo será rápido, pero a medida que su entrada crezca tardará un poco más.

O (1) y O (logn) hacen una gran diferencia cuando comienzas a combinar algoritmos.

Realice haciendo uniones con índices, por ejemplo. Si pudieras hacer un join en O (1) en lugar de O (logn) obtendrías grandes ganancias de rendimiento. Por ejemplo, con O (1) puede unirse a cualquier cantidad de veces y todavía tiene O (1). Pero con O (logn) necesita multiplicar el recuento de operaciones por logn cada vez.

Para entradas grandes, si ya tenía un algoritmo que era O (n ^ 2), preferiría hacer una operación que fuera O (1) dentro y no O (logn) dentro.

También recuerde que Big-O de cualquier cosa puede tener una sobrecarga constante. Digamos que la sobrecarga constante es de 1 millón. Con O (1) esa sobrecarga constante no amplifica el número de operaciones tanto como lo hace O (logn).

Otro punto es que todos piensan en O (logn) que representa n elementos de una estructura de datos de árbol, por ejemplo. Pero podría ser cualquier cosa, incluidos los bytes en un archivo.

La observación de que O(log n) menudo es indistinguible de O(1) es buena.

Como ejemplo familiar, supongamos que quisiéramos encontrar un solo elemento en una matriz ordenada de un 1,000,000,000,000 de elementos:

con búsqueda lineal, la búsqueda toma en promedio 500,000,000,000 pasos
con la búsqueda binaria, la búsqueda toma un promedio de 40 pasos

Supongamos que agregamos un solo elemento a la matriz que estamos buscando, y ahora debemos buscar otro elemento:

con la búsqueda lineal, la búsqueda toma en promedio 500,000,000,001 pasos (cambio indistinguible)
con la búsqueda binaria, la búsqueda toma un promedio de 40 pasos (cambio indistinguible)

Supongamos que duplicamos la cantidad de elementos en la matriz que estamos buscando, y ahora debemos buscar otro elemento:

con la búsqueda lineal, la búsqueda toma un promedio de 1,000,000,000,000 pasos (cambio extraordinariamente notable)
con la búsqueda binaria, la búsqueda toma un promedio de 41 pasos (cambio indistinguible)

Como podemos ver en este ejemplo, para todos los efectos, un algoritmo O(log n) como la búsqueda binaria a menudo es indistinguible de un algoritmo O(1) como la omnisciencia.

El punto de partida es este: * utilizamos algoritmos O(log n) porque a menudo no se distinguen del tiempo constante, y porque a menudo funcionan fenomenalmente mejor que los algoritmos de tiempo lineal.

Obviamente, estos ejemplos asumen constantes razonables. Obviamente, estas son observaciones genéricas y no se aplican a todos los casos. Obviamente, estos puntos se aplican en el extremo asintótico de la curva, no en el extremo n=3 .

Pero esta observación explica por qué, por ejemplo, utilizamos técnicas como ajustar una consulta para realizar una búsqueda de índice en lugar de una exploración de tabla, porque una búsqueda de índice opera en tiempo casi constante sin importar el tamaño del conjunto de datos, mientras que una exploración de tabla es aplastantemente lento en conjuntos de datos suficientemente grandes. La búsqueda de índice es O(log n) .

Las reglas para determinar la notación Big-O son más simples cuando no se decide que O (log n) = O (1).

Como dijo krzysio, puedes acumular O (log n) s y luego harían una diferencia muy notable. Imagine que hace una búsqueda binaria: comparaciones O (log n), y luego imagine que la complejidad de cada comparación O (log n). Si descuida ambos, obtendrá O (1) en lugar de O (log ² n). De manera similar, de alguna manera puede llegar a O (log ¹⁰ n) y luego notará una gran diferencia para las "n" s no demasiado grandes.

No creo en algoritmos donde pueda elegir libremente entre O (1) con una constante grande y O (logN) realmente existe. Si hay N elementos con los que trabajar al principio, es simplemente imposible hacerlo O (1), lo único que es posible es mover su N a alguna otra parte de su código.

Lo que trato de decir es que en todos los casos reales que conozco, usted tiene alguna compensación de espacio / tiempo, o algún pretratamiento, como compilar datos en una forma más eficiente.

Es decir, realmente no vas O (1), solo mueves la parte N a otra parte. O intercambias el rendimiento de alguna parte de tu código con alguna cantidad de memoria o bien intercambias el rendimiento de una parte de tu algoritmo con otra. Para mantenerse sano siempre debe mirar la imagen más grande.

Mi punto es que si tienes N elementos, no pueden desaparecer. En otras palabras, puede elegir entre algoritmos ineficientes O (n ^ 2) o peor y O (n.logN): es una elección real. Pero nunca vas realmente a O (1).

Lo que intento señalar es que para cada problema y estado de datos inicial hay un ''mejor'' algoritmo. Puedes hacerlo peor pero nunca mejor. Con algo de experiencia, puede tener una buena idea de qué es esta complejidad intrínseca. Entonces, si su tratamiento general coincide con la complejidad, sabe que tiene algo. No podrá reducir esa complejidad, sino solo moverla.

Si el problema es O (n) no se convertirá en O (logN) u O (1), simplemente agregará un pretratamiento de tal manera que la complejidad general no se modifique o empeore, y potencialmente se mejorará un paso posterior. Digamos que quiere el elemento más pequeño de una matriz, puede buscar en O (N) u ordenar la matriz con cualquier tratamiento de clasificación O (NLogN) común y luego usar la primera O (1).

¿Es una buena idea hacer eso casualmente? Solo si su problema requiere también elementos de segundo, tercero, etc. Entonces su problema inicial fue realmente O (NLogN), no O (N).

Y no es lo mismo si espera diez veces o veinte veces más para su resultado porque simplificó diciendo O (1) = O (LogN).

Estoy esperando un contraejemplo ;-) que es un caso real en el que puede elegir entre O (1) y O (LogN) y donde cada paso O (LogN) no se compara con O (1). Todo lo que puede hacer es tomar un algoritmo peor en lugar del natural o mover un poco de tratamiento pesado a alguna otra parte de las imágenes más grandes (resultados de precomputación, espacio de almacenamiento, etc.)

O (log N) puede ser engañoso. Tomemos por ejemplo las operaciones en árboles Rojo-Negros .
Las operaciones son O (logN) pero bastante complejas, lo que significa muchas operaciones de bajo nivel.

O (logN) * O (logN) * O (logN) es muy diferente. O (1) * O (1) * O (1) sigue siendo constante. También un O de estilo quicksort simple (nlogn) es diferente de O (n O (1)) = O (n). Intenta ordenar 1000 y 1000000 elementos. Este último no es 1000 veces más lento, es 2000 veces, porque log (n ^ 2) = 2log (n)

Para N lo suficientemente pequeño, O (N ^ N) puede reemplazarse en la práctica con 1. No O (1) (por definición), pero para N = 2 puede verse como una operación con 4 partes, o un tiempo constante operación.

¿Qué pasa si todas las operaciones toman 1 hora? La diferencia entre O (log N) y O (1) es grande, incluso con N pequeño.

¿O si necesita ejecutar el algoritmo diez millones de veces? Ok, eso tomó 30 minutos, así que cuando lo ejecuto en un conjunto de datos cien veces más grande todavía debería tomar 30 minutos porque O (logN) es "lo mismo" que O (1) ... eh ... ¿qué?

Su afirmación de que "entiendo O (f (N))" es claramente falsa.

Aplicaciones del mundo real, oh ... No sé ... CADA USO DE O () - Notación?

Búsqueda binaria en una lista ordenada de 10 millones de elementos, por ejemplo. Es la RAZÓN misma que utilizamos las tablas hash cuando los datos son lo suficientemente grandes. Si crees que O (logN) es lo mismo que O (1), ¿por qué usarías NUNCA un hash en lugar de un árbol binario?

Para cualquier algoritmo que pueda tomar entradas de diferentes tamaños N, el número de operaciones que realiza está limitado por alguna función f (N).

Todo lo que Big-O te dice es la forma de esa función.

O (1) significa que hay un número A tal que f (N) <A para N grande
O (N) significa que hay algunos A tales que f (N) <AN para N grande
O (N ^ 2) significa que hay algunos A tales que f (N) <AN ^ 2 para N. grande
O (log (N)) significa que hay algunos A tales que f (N) <AlogN para N. grande

Big-O no dice nada sobre cuán grande es A (es decir, qué tan rápido es el algoritmo), o dónde estas funciones se cruzan entre sí. Solo dice que cuando comparas dos algoritmos, si sus big-Os difieren, entonces hay un valor de N (que puede ser pequeño o puede ser muy grande) donde un algoritmo comenzará a superar al otro.

Sí, log (N) <100 para la mayoría de los propósitos prácticos, y No, no siempre puede reemplazarlo por constante.

Por ejemplo, esto puede conducir a errores graves al estimar el rendimiento de su programa. Si el programa O (N) procesa una matriz de 1000 elementos en 1 ms, entonces está seguro de que procesará 10 ⁶ elementos en 1 segundo (más o menos). Sin embargo, si el programa es O (N * logN), tomará ~ 2 segundos procesar 10 ⁶ elementos. Esta diferencia puede ser crucial; por ejemplo, puede pensar que tiene suficiente poder de servidor porque obtiene 3000 solicitudes por hora y cree que su servidor puede manejar hasta 3600.

Otro ejemplo. Imagine que tiene la función f () trabajando en O (logN) y en cada función de llamada de iteración g (), que también funciona en O (logN). Entonces, si reemplaza ambos registros por constantes, cree que su programa funciona en tiempo constante. Sin embargo, la realidad será cruel: dos registros pueden darte hasta 100 * 100 multiplicadores.

Suponga que en toda su aplicación, un algoritmo representa el 90% del tiempo que el usuario espera para la operación más común.

Supongamos que en tiempo real la operación O (1) tarda un segundo en su arquitectura, y la operación O (logN) es básicamente .5 segundos * log (N). Bueno, en este punto me gustaría dibujar un gráfico con una flecha en la intersección de la curva y la línea, diciendo: "Importa aquí". Desea usar el log (N) op para conjuntos de datos pequeños y el O (1) op para conjuntos de datos grandes, en tal escenario.

La notación de Big-O y la optimización del rendimiento es un ejercicio académico en lugar de ofrecer un valor real al usuario para operaciones que ya son baratas, pero si se trata de una operación costosa en un camino crítico, ¡entonces se puede apostar a que es importante!

Supongamos que utiliza un algoritmo de procesamiento de imágenes que se ejecuta en O (log N), donde N es el número de imágenes. Ahora ... afirmar que se ejecuta en tiempo constante le haría creer a uno que no importa cuántas imágenes haya, aún completaría su tarea en la misma cantidad de tiempo. Si ejecutar el algoritmo en una sola imagen tomaría hipotéticamente un día entero, y suponiendo que O (logN) nunca será más de 100 ... imagine la sorpresa de esa persona que trataría de ejecutar el algoritmo en una base de datos de imágenes muy grande - Esperaría que se hiciera en un día más o menos ... sin embargo, llevará meses terminarlo.

Usted pidió un ejemplo del mundo real. Te daré uno. Biología Computacional. Una hebra de ADN codificada en ASCII está en algún lugar en el nivel de gigabytes en el espacio. Una base de datos típica obviamente tendrá muchos miles de tales hilos.

Ahora, en el caso de un algoritmo de indexación / búsqueda, ese log (n) múltiple hace una gran diferencia cuando se combina con constantes. ¿La razón por la cual? Esta es una de las aplicaciones donde el tamaño de tu entrada es astronómico. Además, el tamaño de entrada siempre seguirá creciendo.

Es cierto que este tipo de problemas son raros. Solo hay tantas aplicaciones tan grandes. En esas circunstancias, sin embargo ... hace un mundo de diferencia.

tienes razón, en muchos casos no importa para propósitos prácticos. pero la pregunta clave es "qué tan rápido CRECE N". la mayoría de los algoritmos que conocemos toman el tamaño de la entrada, por lo que crece linealmente.

pero algunos algoritmos tienen el valor de N derivado de una manera compleja. si N es "la cantidad de posibles combinaciones de lotería para una lotería con X números distintos", de repente importa si su algoritmo es O (1) u O (logN)

En teoria

Sí, en situaciones prácticas log (n) está limitado por una constante, diremos 100. Sin embargo, reemplazar log (n) por 100 en situaciones en las que es correcto sigue arrojando información, haciendo el límite superior en las operaciones que tiene calculado más flojo y menos útil. Reemplazar una O (log (n)) por una O (1) en su análisis podría resultar en que su n caso grande sea 100 veces peor de lo esperado en función de su pequeño n caso. Su análisis teórico podría haber sido más preciso y podría haber predicho un problema antes de construir el sistema.

Yo diría que el propósito práctico del análisis de gran O es intentar y predecir el tiempo de ejecución de su algoritmo lo antes posible. Puede facilitar su análisis tachando los términos de registro (n), pero luego ha reducido el poder predictivo de la estimación.

En la práctica

Si lees los documentos originales de Larry Page y Sergey Brin en la arquitectura de Google, hablan sobre el uso de tablas hash para todo, para garantizar que, por ejemplo, la búsqueda de una página web en caché solo requiera una búsqueda en el disco duro. Si utilizó índices de árbol B para buscar, es posible que necesite cuatro o cinco intentos de disco duro para realizar una búsqueda sin almacenamiento en caché [*]. Cumplir los requisitos de disco de cuádruple en el almacenamiento de la página web almacenada en caché vale la pena preocuparse desde una perspectiva empresarial, y predecible si no se eliminan todos los términos O (log (n)).

PD: Lo siento por usar Google como ejemplo, son como Hitler en la versión informática de la ley de Godwin .

[*] Suponiendo que 4KB se lee desde el disco, 100 mil millones de páginas web en el índice, ~ 16 bytes por clave en un nodo del árbol B.