La utilidad de la comparación es la siguiente: No importa que cambies los "parámetros", sigues llegando al mismo factor de crecimiento general. Sí, 1000n es 1000 veces mayor que n. Eso es obvio. ¿Pero qué pasa si actualizas tu cpu o lo ejecutas en dos hilos? ¿Qué pasa entonces? Bueno, INDEPENDIENTEMENTE, los algoritmos se seguirán comportando de la misma manera. n y 3n y 9n y 0,3432n todos se comportarán de la misma manera independientemente de que el proceso se ejecute" porque el proceso depende linealmente de n.
Lo que nos dice O(n) es precisamente cuánto tiempo necesita el algoritmo para engullir cada vez más datos.
Por ejemplo, supongamos que tenemos un algoritmo A que toma un conjunto de datos S y da como resultado T. Podemos representarlo como T = SA donde podemos usar notación polaca inversa para expresar cualquier complejo de algoritmos, por ejemplo 'T = SAB+RBAAA' donde puedes interpretar las operaciones como quieras (simplemente léelo de izquierda a derecha).
Entonces el rendimiento absoluto de los algoritmos podría cambiar con diferentes cpus, digamos, si todos están en la misma clase bajo equivalencia O(n) todos corren igual(bajo equivalencia, no igualdad absoluta).
Piénsalo con más delicadeza: Sea A_k el algoritmo en su "paso k". Otro algoritmo que procese exactamente los mismos datos sería el algoritmo en el paso B_k.
Entonces O(n) nos dice que A_{k+1}/A_k y B_{k+1}/B_k son ambos de la misma clase. O(n) es en realidad la clase de equivalencia para cualquier familia de funciones que crezcan todas a la misma tasa funcional.
Por ejemplo, supongamos que A_k tarda 20 segundos en pasar al estado A_{k+1} y 15 segundos en pasar del estado A_{k+1} a A_{k+2}. Supongamos que tenemos un ordenador más rápido que ejecuta A, al que llamaremos B. Ahora B_k tarda 15 segundos en ir al estado B_{k+1} y 11,3184 segundos en ir del estado B_{k+1} a B_{k+2}.
Entonces 15/20 = 0,75 = 11,3184/15.
Es decir, ambas máquinas requieren la misma proporción relativa de trabajo. Comparamos solo los algoritmos, no el hardware en el que se ejecutan.
Ahora bien, en realidad, O(n) no es exactamente lo que he descrito antes, pero sigue la misma idea de que queremos poder decir que dos cosas son iguales aunque no lo sean.
¿Por qué? Porque en muchos problemas no necesitamos conocer el comportamiento exacto de una función, sino sólo cómo se comporta en general. Por ejemplo, en problemas de convergencia quizá sólo queramos demostrar que algo converge. En este caso no necesitamos conocer el comportamiento local. Si tenemos una función dominante y sabemos que el operador de sustitución de la función dominante es una identidad en el operador límite, entonces podemos calcular y hacer límites mucho más fácilmente. ¡Rápido! ¿Cuál es el límite de 1/x*(cos(x)*3 + 1/x^cos(3x)) cuando x-> oo? Bueno, una aplicación de O(n)-nastics mental puede decir rápidamente que es probablemente 0. En lugar de preocuparse por toda la basura después de 1/x sólo podemos usar 1/x porque, en lo que respecta al límite, ambos son el mismo resultado (el límite los envía a la misma clase de equivalencia).
el límite 3/x es exactamente el mismo que el límite 2/x cuando x->oo. Igual que $3x + 4$ es exactamente la misma expresión que 2x + cos(30.43Pi). Ambas son expresiones lineales. Son EXACTAS bajo ese nivel de abstracción.
Aquí hacemos exactamente lo mismo, pero con tasas de crecimiento de las funciones. Pero no sus tasas de crecimiento exactas, sino su "forma" básica. Por ejemplo, podemos pensar que todas las rectas crecen al mismo ritmo. Igual que todas las parábolas. Aunque $3x^2$ técnicamente crece más rápido que $x^2$ las consideramos iguales porque la tasa de variación del crecimiento es en realidad constante con respecto a la función de base (piénsese en el caso lineal). Por supuesto, entonces podemos combinar clases como términos lineales y cuadráticos. $x^2 + 3x$ . Pues bien, dado que nos ocupamos de x grandes y ya hemos demostrado que $x^2$ dominantes $3x$ (podemos poner cualquier forma más dominante y seguir obteniendo una forma dominante) podemos decir ignorar las partes "sumisas". Ej, $x^2 + 3x == x^2 == 3x^2 = x^2 + cos(3x) == ...$ .
Para recapitular, si tomamos nuestro algoritmo A, tiene una cierta velocidad de ejecución exacta que se podría trazar en un gráfico. Pero si actualizas el hardware ese gráfico cambiará. Aunque probablemente sólo se verá como un gráfico a escala.
Pero digamos que ahora lo ejecutas en un sistema operativo diferente y que ese sistema operativo diferente realiza diferentes tipos de programación, por lo que tu gráfico no tiene el mismo aspecto. PERO existe el mismo patrón general que antes... al menos en carreras largas ¡!
Por tanto, la notación O(n) nos permite hablar de estas cuestiones con mayor precisión. Es una forma de clasificar el conjunto de funciones en una partición/relación de equivalencia útil y luego aplicarlas para encontrar consecuencias más útiles.
En tu mente es "¿Por qué estamos haciendo las cosas tan complejas sólo para hablar de rendimiento en tiempo de ejecución? No tiene sentido". El algoritmo A tarda 10 segundos en calcular S y el algoritmo B tarda 34,432 segundos. El algoritmo A es mejor". Pero esa no es una métrica útil. ¿Por qué es mejor A? ¿Sólo porque se ejecuta más rápido en tu ejemplo? Tal vez no es realmente más rápido, sino que sólo tiene un mejor rendimiento en tiempos de ejecución pequeños (conjuntos de datos pequeños), ya que utiliza el almacenamiento en caché y luego se convierte en el peor algoritmo del planeta. ¿Y entonces qué? Saber que A domina a B en O(n) nos dice que B funciona mejor a largo plazo.
Al pensar en términos de O(n) estás pensando en formas más generales en que las funciones se relacionan (es algo así como con la topología puedes pensar en cómo diferentes funciones son equivalentes (bajo transformaciones homeomórficas)). También estás pensando de forma más "futurista", en el sentido de que tu "hardware" se actualizará automáticamente. Por ejemplo, si diseñas algoritmos basados en fundamentos O(n), puedes saber si tus algoritmos son terribles o no, independientemente de la máquina en la que se ejecuten. A medida que las máquinas se vuelvan más rápidas, los algoritmos seguirán teniendo el mismo "rango" que antes. Así que estás comparando algoritmos en su diseño general y no en aspectos específicos que pueden cambiar en cualquier momento.
Es algo así como la inversa de Taylor. Con las series de Taylor añadimos términos para obtener más y más términos = más y más precisión. Con O(n) queremos hacer lo mismo pero añadir menos y obtener más dominio. Por ejemplo, 1 -> 1 + 2n -> 1 + 2n + n^2 vs 1 + 2n + n^2 -> 2n + n^2 -> n^2.
Aunque la definición técnica y el uso son más "legales", la clave está en transmitir la idea de que se trata de algo diferente y más útil. Lamentablemente, se limitan a dar las definiciones sin explicar por qué fue útil crearlas, y a la mayoría de la gente se le enseñan las definiciones EN VEZ DE las experiencias que condujeron a la definición. [Por ejemplo, no te dan ningún contexto o muy poco, lo que significa que es casi seguro que no lo vas a entender a menos que tengas algunas experiencias que te lo permitan. ]
Gran parte de las matemáticas tienen la necesidad de comparar cosas de forma "vaga". Es decir, hay alguna superposición que queremos entender, pero la forma en que la representamos actualmente dificulta la discusión. Se crea entonces la maquinaria para poder transformar(se construyen transformaciones) el problema en una forma diferente de pensar sobre él.
Es decir, una vez que te das cuenta de que comparar el rendimiento de los algoritmos (que no es más que el comportamiento a largo plazo en matemáticas) es inútil, sigues necesitando alguna forma de compararlos. La necesidad de compare nunca desapareció, sólo la comprensión de que la representación era insuficiente. De ahí que sea necesaria una nueva representación y, por tanto, un nuevo lenguaje, lo que implica definiciones y sus términos. Una vez hecho esto para los algoritmos, llegamos al concepto de representar (hablar de) algoritmos en términos de su "comportamiento a largo plazo". No nos importa la fluctuación inicial ni las aberraciones menores... sólo el comportamiento general a largo plazo.
Las definiciones van definiendo con precisión lo que quieren decir con eso.