big-o - leibniz - para que sirve el calculo diferencial

¿Puede un algoritmo O(n) exceder O(n ^ 2) en términos de tiempo de cálculo? (6)

En resumen, sí, puede. La definición de O se basa en el hecho de que O(f(x)) < O(g(x)) implica que g(x) tomará definitivamente más tiempo para ejecutar que f(x) dada una x suficientemente grande.

Por ejemplo, es un hecho conocido que para los valores pequeños, el tipo de combinación se supera por clasificación por inserción (si recuerdo correctamente, debería ser cierto para n menor que 31 )

Supongamos que tengo dos algoritmos:

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { //do something in constant time } }

Esto es, naturalmente, O(n^2) . Supongamos que también tengo:

for (int i = 0; i < 100; i++) { for (int j = 0; j < n; j++) { //do something in constant time } }

Esto es O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

Parece que a pesar de que mi segundo algoritmo es O(n) , tomará más tiempo. ¿Alguien puede ampliar esto? Lo menciono porque a menudo veo algoritmos donde, por ejemplo, realizarán primero un paso de clasificación o algo así, y al determinar la complejidad total, es simplemente el elemento más complejo que limita el algoritmo.

La única garantía que obtienes es que, sin importar los factores constantes, para n suficientemente grande, el algoritmo O (n) gastará menos operaciones que el O (n ^ 2).

Como ejemplo, vamos a contar las operaciones en el ejemplo claro de OPs. Sus dos algoritmos se diferencian en una sola línea:

for (int i = 0; i < n; i++) { (* A, the O(n*n) algorithm. *)

vs.

for (int i = 0; i < 100; i++) { (* B, the O(n) algorithm. *)

Como el resto de sus programas son iguales, la diferencia en el tiempo de ejecución real se decidirá por estas dos líneas.

Para n = 100, ambas líneas hacen 100 iteraciones, por lo que A y B realizan exactamente lo mismo en n = 100.
Para n <100, digamos, n = 10, A solo hace 10 iteraciones, mientras que B hace 100. Claramente, A es más rápido.
Para n> 100, digamos, n = 1000. Ahora el bucle de A hace 1000 iteraciones, mientras que el bucle B todavía hace sus 100 iteraciones fijas. Claramente, A es más lento.

Por supuesto, qué tan grande tiene que llegar n para que el algoritmo O (n) sea más rápido depende del factor constante. Si cambia la constante de 100 a 1000 en B, entonces el corte también cambia a 1000.

La complejidad asintótica (que es lo que representan tanto Big-O como Big-Theta) ignora por completo los factores constantes implicados; solo tiene como objetivo dar una indicación de cómo cambiará el tiempo de ejecución a medida que el tamaño de la entrada se hace más grande.

Por lo tanto, es posible que un algoritmo Θ(n) pueda llevar más tiempo que un Θ(n ² ) para un n dado, lo que ocurrirá realmente dependerá de los algoritmos involucrados, para su ejemplo específico, este será el caso para n < 100 , ignorando la posibilidad de optimizaciones que difieren entre los dos.

Para cualquiera de los dos algoritmos dados que toman Θ(n) y Θ(n ² ) tiempo respectivamente, lo que es probable que veas es que:

El algoritmo Θ(n) es más lento cuando n es pequeño, luego el Θ(n ² ) uno se vuelve más lento a medida que n aumenta
(lo que sucede si el Θ(n) uno es más complejo, es decir, tiene factores constantes más altos), o
El Θ(n ² ) uno siempre es más lento.

Aunque es posible que el algoritmo Θ(n) sea más lento, el Θ(n ² ) uno, luego el Θ(n) uno otra vez, y así sucesivamente a medida que n aumenta, hasta que n hace muy grande, desde ese punto en adelante el Θ(n ² ) uno siempre será más lento, aunque es muy poco probable que suceda.

En términos ligeramente más matemáticos:

Digamos que el algoritmo Θ(n ² ) toma cn ² operaciones para algunos c .

Y el algoritmo Θ(n) toma operaciones dn para algunos d .

Esto está en línea con la definición formal, ya que podemos suponer que esto se cumple para n mayor que 0 (es decir, para todo n ) y que las dos funciones entre las cuales el tiempo de ejecución es mentiras es la misma.

De acuerdo con su ejemplo, si dijera c = 1 d = 100 , entonces el algoritmo Θ(n) sería más lento hasta n = 100 , en cuyo punto el algoritmo Θ(n ² ) se volvería más lento.

_{(cortesía de WolframAlpha )} .

Nota de notación:

Técnicamente grande-O es solo un límite superior, lo que significa que se puede decir que un algoritmo O(1) (o realmente cualquier algoritmo que tome O(n ² ) o menos tiempo) también toma O(n ² ) . Por lo tanto, en su lugar utilicé la notación grande-Theta (Θ), que es solo un límite apretado. Ver las definiciones formales para más información.

Big-O a menudo se trata de manera informal o se le enseña a ser un límite apretado, por lo que es posible que ya haya utilizado esencialmente Big-Theta sin saberlo.

Si hablamos de un límite superior solamente (según la definición formal de big-O), eso sería más bien una situación de "todo vale" - el O(n) uno puede ser más rápido, el O(n ² ) uno pueden ser más rápidos o pueden tomar la misma cantidad de tiempo (asintóticamente); por lo general, no se pueden sacar conclusiones particularmente significativas con respecto a la comparación del big-O de los algoritmos, solo se puede decir que, dada una gran O de algún algoritmo , que ese algoritmo no tomará más tiempo que esa cantidad de tiempo (asintóticamente).

Los grandes O(n) no están destinados a comparar la velocidad relativa de un algoritmo diferente. Están destinados a medir qué tan rápido aumenta el tiempo de ejecución cuando aumenta el tamaño de la entrada. Por ejemplo,

O(n) significa que si n multiplica por 1000, entonces el tiempo de ejecución se multiplica aproximadamente por 1000.
O(n^2) significa que si n se multiplica por 1000, entonces la carrera se multiplica aproximadamente por 1000000.

Entonces, cuando n es lo suficientemente grande, cualquier algoritmo O(n) vencerá a un algoritmo O(n^2) . No significa que nada para un n fijo.

Sí. El O () significa solo complejidad asintótica. El algoritmo lineal puede ser más lento que el cuadrático, si tiene una constante lineal de desaceleración bastante grande (si el núcleo del ciclo funciona 10 veces más, será más lento que su versión cuadrática).

La notación O () es solo una extrapolación, aunque bastante buena.

Sí , un algoritmo O (n) puede exceder un algoritmo O (n ² ) en términos de tiempo de ejecución. Esto sucede cuando el factor constante (que omitimos en la notación O grande) es grande . Por ejemplo, en su código anterior, el algoritmo O (n) tendrá un factor constante grande. Por lo tanto, funcionará peor que un algoritmo que se ejecuta en O (n ² ) para n <10.

Aquí, n = 100 es el punto de cruce. Entonces, cuando una tarea puede realizarse en O (n) y en O (n ² ) y el factor constante del algoritmo lineal es más que el de un algoritmo cuadrático, entonces tendemos a preferir el algoritmo con el peor tiempo de ejecución. Por ejemplo, al ordenar una matriz, cambiamos a ordenar por inserción para las matrices más pequeñas, incluso cuando la ordenación por fusión o la ordenación rápida se ejecutan de manera más rápida. Esto se debe a que el ordenamiento por inserción tiene un factor constante menor que la combinación / clasificación rápida y se ejecutará más rápido.