Big O notación prueba matemática [cerrado] - algoritmo, big-o

Estoy tratando de entender qué es exactamente Big OLa notación es. Lo entiendo en el sentido literal y práctico al analizar las respuestas de preguntas similares en SO. Pero lo que las respuestas no explican y no entiendo es la base matemática detrás de esto. La definición formal establece que

  A function T(n) is the Big-O notation of f(n), if and only if there exist two constants c, n0 > 0 such that

T(n) <= c * f(n)  for all n >= n0.

Entiendo intuitivamente hasta cierto punto que estoLa ecuación trata de calcular el límite superior en términos de alguna función que tiene mayor pendiente en el sentido, algo en el extremo superior de la función f (n). Sé que mi comprensión es vaga. Entonces, ¿puede alguien explicar las bases / representaciones matemáticas de la notación Big-O?

Respuestas

Primero déjame decir que si g (n) es una función de norte, entonces O (g (n)) es el conjunto de todas las funciones f (n) de tal manera que existen constantes c, N> 0 tal que f (n) <= cg (n) para todos n> = N.

Si uno analiza un algoritmo exactamente, entonces uno viene con una función del tamaño de entrada nortedecir f (n), lo que podría ser una expresión polinómica molesta complicada en norte (o una expresión complicada que implique un exponencial).

Por ejemplo, uno podría encontrar que un algoritmo, dado un tamaño de entrada de norte, tiene exactamente f (n) = 2n ^ 2 + 3n + 1 instrucciones. Pero no nos importa mucho el 3n + 1 parte. Si norte se vuelve muy grande, el n ^ 2 término de F dominará los términos de orden inferior. Por ejemplo, para n = 100 ya encontramos que 2 * 100 ^ 2 es mucho más significativo que 3 * 100 + 1.

Entonces, para hacer esta idea más rigurosa, "nos gustaría decir eso"f (n) crece en el peor de los casos como n ^ 2 ". En notación matemática: f (n) es un elemento de O (n ^ 2). Ahora, como usted ha indicado en su pregunta, paraEn realidad, si probamos que f (n) es un elemento de O (n ^ 2), necesitamos encontrar las constantes c y N de tal manera que para todos n> = N tenemos f (n) <= cn ^ 2. Entonces, si probamos c = 3, obtenemos la desigualdad f (n) <= 3 * n ^ 2, y si juegas algebraicamente, encontrarás que para todo n> = 5 esto es cierto. Así que nuestra c = 3 y nuestro N = 5. De hecho, f (n) crece en el peor de los casos como n ^ 2.

Note sin embargo las palabras en el peor de los casos. Sería un error decir "f (n) crece como ..."en cambio decimos "f (n) crece en el peor de los casos como ... ".

Para darle otro ejemplo, considere nuestra f (n) = 2n ^ 2 + 3n + 1 otra vez. Mi reclamo es que f (n) no es un elemento de O (n). Para demostrar que esto es verdad, necesitamosmuestra que para todo c, N> 0 existe n> = N tal que f (n)> cn. Bueno, f (n)> cn es verdadero si y solo si 2n ^ 2 + (3-c) n + 1> 0, que es cierto para n suficientemente grande = N (= no importa lo que sea N), del cual Te dejaré trabajar los detalles. Esto demuestra que f (n) Crece a una velocidad peor que la lineal.

Otro ejemplo más con nuestro f (n) = 2n ^ 2 + 3n + 1: Se puede demostrar que f (n) es un elemento deO (n ^ 3). Vamos a hacer eso, ¿vale? Necesitamos encontrar c, N> 0 tal que f (n) <= cn ^ 3 para todos n> = N. Bueno, intente c = 1; luego, después de algún álgebra, puede encontrar que esto es cierto para N = 4. Esto garantiza que el sentimiento "f (n) crece en el peor de los casos como ..."; si puede demostrar que su función f está en una gran O, entonces podría haber un "mejor big big" O "de la que forma parte.

Como ejercicio final, demuestre que O (1) es un apropiado subconjunto de O (n), que es un apropiado subconjunto de O (n ^ 2), que es un apropiado subconjunto de O (n ^ 3), que es un apropiado subconjunto de O (n ^ 4), ...

g (n) = O (f (n)) significa que después de un cierto n (para n> n0) g (n) / f (n) <= M (una cantidad fija) Por ejemplo, g (n) = n es O (n) y O (n * log (n)) como para n0 = 2:

n / n = 1 <= 1 = M

n / (n * log (n)) <= 1 / log (2) = M