algorithm - para - little big city play store
¿Big O mide los requisitos de memoria o simplemente acelera? (8)
Big O es realmente solo una medida del crecimiento de la complejidad basado en el crecimiento de la entrada. Dos algoritmos con ambos O (n) pueden ejecutarse en tiempos muy diferentes, pero su crecimiento es lineal en relación con el crecimiento de la entrada.
A menudo aquí la gente habla de Big O que mide los algoritmos entre sí.
¿Esto mide ciclos de reloj o requisitos de espacio?
Si la gente quiere contrastar algoritmos basados en el uso de la memoria, ¿qué medida utilizarían?
Big O es solo una herramienta matemática que se puede usar para describir cualquier función. Por lo general, la gente lo usa para describir la velocidad, pero también puede usarse para describir el uso de la memoria.
Además, cuando usamos Big O por tiempo, generalmente no estamos hablando directamente sobre ciclos de reloj. En cambio, contamos las "operaciones básicas" (que se asume implícitamente que llevan un número constante de ciclos).
Big O y otros se utilizan para medir el crecimiento de algo.
Cuando alguien dice que algo es O(N) , entonces esa cosa no crece más rápido que la tasa lineal. Si algo es Ω(N^2) , entonces esa cosa no crece más lentamente que la velocidad cuadrática. Cuando algo es Θ(2^N) , entonces esa cosa crece a una velocidad exponencial.
Lo que es eso puede ser el requisito de tiempo para un algoritmo. También puede ser el espacio, es decir, el requisito de memoria para un algoritmo. También puede ser prácticamente cualquier cosa, relacionada con el espacio y el tiempo.
Por ejemplo, algunos algoritmos masivamente paralelos a menudo miden la escalabilidad en la cantidad de procesadores en los que se puede ejecutar. Un algoritmo particular puede ejecutarse en procesadores O(N) en tiempo O(N^2) . Otro algoritmo puede ejecutarse en procesadores O(N^2) en tiempo O(N) .
Preguntas relacionadas
Ver también
Big-O puede usarse para describir la relación entre dos cantidades cualesquiera. Aunque generalmente solo se utiliza en informática, el concepto también puede ser aplicable en otros campos como la física. Por ejemplo, la cantidad de potencia que se debe colocar en una antena de un tamaño determinado para producir una señal de intensidad de unidad a cierta distancia es O (d ^ 2), independientemente de la forma de la antena. Si el tamaño de la antena es grande en relación con la distancia, el aumento en la fuerza requerida puede ser lineal o incluso sublineal en lugar de cuadrático, pero a medida que la distancia se hace más grande, el término cuadrático dominará.
Mientras que normalmente los algoritmos compiten a tiempo, entonces normalmente asumo que cualquier declaración O era la hora. Sin embargo, es perfectamente válido comparar también el espacio. O se puede usar para cualquier medición, normalmente usamos la velocidad porque normalmente es la más importante.
Normalmente es el número de operaciones, lo que se traduce en velocidad. Normalmente, los algoritmos difieren más en velocidad que en uso de memoria. Sin embargo, verá la notación O () utilizada para el uso de la memoria, cuando corresponda.
Respuesta corta: tienes ''Big O en el espacio "y" Big O en el tiempo ".
Respuesta larga: Big O es solo una notación, puedes usarla en el contexto que desees.
Si alguien dice "Este algoritmo se ejecuta en O (n)", está hablando de velocidad. Si alguien dice "Este algoritmo se ejecuta en el espacio O (n)", está hablando de memoria.
Si solo dice "Este algoritmo es O (n)", generalmente está hablando de velocidad (aunque si lo dice durante una discusión sobre la memoria, probablemente esté hablando de la memoria).
Si no estás seguro de a quién se refiere alguien, pregúntale.