La notación Big Oh no menciona un valor constante

O (n) y otra notación de orden (típicamente) no se ocupa del comportamiento de las funciones para valores pequeños. Se ocupa del comportamiento de las funciones para valores muy grandes, es decir, límites a medida que n avanza hacia el infinito.

Las constantes técnicamente son importantes, pero normalmente se abstraen, ya que una vez que n es lo suficientemente grande, el valor de c es totalmente irrelevante. Si el valor de c es importante, podemos incluirlo en el análisis, pero a menos que las funciones que se comparan tengan factores constantes muy grandes o si la eficiencia es una preocupación especialmente importante, generalmente no lo son.

Hay varias razones, pero probablemente la más importante es que las constantes son una función de la implementación del algoritmo, no el algoritmo en sí. El orden de un algoritmo es útil para comparar algoritmos independientemente de su implementación.

El tiempo de ejecución real de un quicksort generalmente cambiará si se implementa en C o Python o Scala o PostScript. Lo mismo se aplica a tipo burbuja : el tiempo de ejecución variará ampliamente según la implementación.

Sin embargo, lo que no cambiará es el hecho de que, al igual que todo lo demás, a medida que el conjunto de datos aumenta, el tiempo requerido para ejecutar una clasificación de burbujas aumentará más rápido que el tiempo requerido para ejecutar el ordenamiento rápido el caso típico, independientemente del idioma o la máquina con la que se implementen, suponiendo una implementación razonablemente correcta. Este simple hecho le permite hacer inferencias inteligentes sobre los algoritmos cuando no hay detalles concretos disponibles.

El orden de un algoritmo filtra factores que, si bien son importantes en las mediciones reales del mundo real, tienden a ser solo ruido cuando se comparan algoritmos en el resumen.

La notación Big O según la definición indica que:
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}
La notación Big O se basa en la intuición de que para todos los valores n en y a la derecha de n ', el valor de f (n) está en o por debajo de c.g (n).
Las constantes tampoco importan cuando se usan factores de alto valor (variables) (como n-cuadrado o n-cubo), ya que son solo las constantes y no las cantidades variables que pueden llegar a ser tan grandes como esos factores. A continuación se muestra el gráfico de la notación Big-O.

Laesenciadeestanotaciónestáenelhechode" how lower is f(n) from c.g(n) and not when it starts becoming lower ".

En el análisis de algoritmos, Orden de crecimiento es la abstracción clave y proporciona la velocidad a la que cambia el tiempo de ejecución a medida que cambia el tamaño de la entrada. Digamos que un algoritmo tiene un tiempo de ejecución f(n) = 2n + 3 . Ahora conectamos un tamaño de entrada,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Como puede verse, el orden de crecimiento está determinado principalmente por la variable n ; las constantes 2 y 3 son menos significativas y, a medida que aumenta el tamaño de la entrada, se vuelven aún menos significativas para determinarla. Por eso, en el análisis de algoritmos, las constantes se disminuyen a favor de la variable que determina el orden de crecimiento de una función.

(ya que esta es una respuesta más larga, lee la negrita para obtener un resumen )

Tomemos tu ejemplo y veamos paso a paso, entendiendo el propósito detrás de lo que estamos haciendo. Comenzamos con su función y el objetivo de encontrar su notación Big Oh:

f(n) = 6n+4

Primero, sea O(g(n)) la notación Big Oh que estamos tratando de encontrar para f(n) . De la definición de Big Oh, necesitamos encontrar un simplificado g(n) donde existan algunas constantes c y n0 donde c*g(n) >= f(n) es verdadero para todos n ' s mayor que n0 .

Primero, vamos a elegir g(n) = 6n + 4 (que daría O(6n+4) en Big Oh). En este caso, vemos que c = 1 y cualquier valor de n0 cumplirán los requisitos matemáticos de nuestra definición de Big Oh, ya que g(n) siempre es igual a f(n) :

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

En este punto hemos cumplido con los requisitos matemáticos. Si nos detuviéramos en O(6n+4) , está claro que esto no es más útil que escribir f(n) , por lo que perdería el verdadero propósito de la notación Big Oh: comprender el tiempo general- ¡La complejidad de un algoritmo! Por lo tanto, avancemos al siguiente paso: la simplificación.

Primero, ¿podemos simplificar el 6n para que Big Oh sea O(4) ? ¡No! (Ejercicio para el lector si no entienden por qué)

Segundo, ¿podemos simplificar el 4 para que el Big Oh sea O(6n) ? ¡Sí! En ese caso, g(n) = 6n , entonces:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

En este punto, vamos a elegir c = 2 ya que entonces el lado izquierdo aumentará más rápido (en 12) que el lado derecho (en 6) para cada incremento de n .

2*6n      >=  6n + 4

Ahora debemos encontrar un n0 positivo donde la ecuación anterior sea verdadera para todos los n 's mayores que ese valor. Como ya sabemos que el lado izquierdo está aumentando más rápido que el derecho, todo lo que tenemos que hacer es encontrar una solución positiva. Por lo tanto, dado que n0 = 2 hace que lo anterior sea cierto, sabemos que g(n)=6n , o O(6n) es una posible notación de Big Oh para f(n) .

Ahora, ¿podemos simplificar el 6 para que el Big Oh sea O(n) ? ¡Sí! En ese caso, g(n) = n , entonces:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Seleccionemos c = 7 ya que la izquierda aumentaría más rápido que la derecha.

7*n         >=  6n + 4

Vemos que lo anterior será cierto para todos los n 's mayor o igual que n0 = 4 . Por lo tanto, O(n) es una posible notación de Big Oh para f(n) . ¿Podemos simplificar más g(n) ? ¡No!

Finalmente, hemos encontrado que la notación Big Oh más simple para f(n) es O(n) . ¿Por qué pasamos por todo esto? Porque ahora sabemos que f(n) es lineal , ya que su notación Big Oh es de complejidad lineal O(n) . Lo bueno es que ¡ahora podemos comparar la complejidad de tiempo de f(n) con otros algoritmos! Por ejemplo, ahora sabemos que f(n) tiene una complejidad de tiempo comparable a las funciones h(n) = 123n + 72 , i(n) = n , j(n) = .0002n + 1234 , etc; porque utilizando el mismo proceso de simplificación descrito anteriormente, todos tienen una complejidad de tiempo lineal de O(n) .

Dulce!!!

Si tiene una función de rendimiento de 6n + 4 , la pregunta relevante es "6, ¿qué?". Como un comentario preguntó: ¿qué representa tu constante? En términos físicos, ¿cuáles son las unidades de tu factor constante?

La razón por la que la notación O () se usa tan ampliamente para describir el rendimiento del algoritmo es que no hay una forma portátil de responder a esa pregunta. Los diferentes procesadores tomarán un número diferente de ciclos de reloj y diferentes cantidades de tiempo para realizar el mismo cálculo elemental, o pueden agrupar los cálculos elementales relevantes de manera diferente. Diferentes lenguajes informáticos, o diferentes descripciones formales e informales, como pseudocódigo, representarán algoritmos de maneras difíciles de comparar directamente. Incluso las implementaciones en el mismo lenguaje pueden representar el mismo algoritmo de diferentes maneras: detalles de formato triviales, como el número de líneas a un lado, generalmente tendrá una amplia variedad de opciones estructurales arbitrarias para implementar cualquier algoritmo dado.

Míralo de otra manera: usamos el "algoritmo" no para describir una implementación en particular, sino para describir una clase completa de implementaciones potenciales del mismo procedimiento general. Esta abstracción ignora los detalles de la implementación a favor de documentar algo de valor general, y el factor de rendimiento constante es uno de estos detalles.

Dicho esto, las descripciones de los algoritmos suelen ir acompañadas de folclore, notas o incluso puntos de referencia reales que describen el rendimiento de las implementaciones reales en el hardware real. Esto le da una idea aproximada del tipo de factor constante que debe esperar, pero también debe tomarse con un grano de sal porque el rendimiento real depende de cosas como la cantidad de trabajo realizado en la optimización de una implementación determinada. Además, a largo plazo, el rendimiento relativo de los algoritmos comparables tiende a desviarse a medida que cambia la arquitectura de los procesadores más recientes y más grandes ...

La noción completa de la notación Big-Oh es específicamente ignorar constantes y presentar la parte más importante de la función que describe el tiempo de ejecución de un algoritmo.

Olvida la definición formal por un momento. ¿Cuál es la función peor (de crecimiento más rápido), n^2 - 5000 o 5000 n + 60000 ? Para n menos que alrededor de 5000, la función lineal es mayor (y, por lo tanto, peor). Más allá de eso (¿valor exacto 5013?), La ecuación cuadrática es más grande.

Ya que hay más (bastante más) números positivos mayores que 5000 que menos, tomamos la cuadrática como la función "más grande" (peor) en general. La notación de orden (Big-Oh, etc.) obliga a que (siempre puede eliminar un constante aditivo y multiplicativo usando esas definiciones).

Por supuesto, las cosas no siempre son simples. A veces, do quieres saber esas constantes. ¿Cuál es mejor tipo de inserción o tipo de burbuja? Ambos son O(n^2) . Pero uno realmente es mejor que el otro. Con un análisis más elaborado, se pueden obtener constantes de las que se está preguntando. Por lo general, es mucho más fácil calcular la función Big-Oh que una función más exacta.

Big-Oh ignora estas constantes para simplificar y facilitar las comparaciones más importantes. Nos gusta la notación porque generalmente no queremos saber sobre las constantes (en su mayoría irrelevantes).