¿Qué definición de tasa de crecimiento asintótica debemos enseñar?

Cuando seguimos los libros de texto estándar, o la tradición, la mayoría de nosotros enseñamos la siguiente definición de notación big-Oh en las primeras clases de una clase de algoritmos: Quizás incluso le demos la lista completa con todos sus cuantificadores:

1. $f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
2. $f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
3. $f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
4. $f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
5. $f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$ .

Sin embargo, dado que estas definiciones no son tan fáciles de trabajar cuando se trata de probar incluso cosas simples como $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$ , la mayoría de nosotros nos movemos rápidamente para presentar el "truco del límite":

1. $f = o(g)$ si $\lim_{n \rightarrow \infty} f(n)/g(n)$ existe y es $0$ ,
2. $f = O(g)$ si $\lim_{n \rightarrow \infty} f(n)/g(n)$ existe y no es $+\infty$ ,
3. $f = \Theta(g)$ si $\lim_{n \rightarrow \infty} f(n)/g(n)$ existe y no es ni $0$ ni $+\infty$ ,
4. $f = \Omega(g)$ si $\lim_{n \rightarrow \infty} f(n)/g(n)$ existe y no es $0$ ,
5. $f = \omega(g)$ si $\lim_{n \rightarrow \infty} f(n)/g(n)$ existe y es $+\infty$ .

Mi pregunta es:

¿Sería una gran pérdida para la enseñanza de una clase de algoritmos de pregrado tomar las condiciones límite como las definiciones de $o$ , $O$ , $\Theta$ , $\Omega$ y $\omega$ ? Eso es lo que todos terminamos usando de todos modos y me parece bastante claro que omitir las definiciones del cuantificador facilita la vida de todos.

Me interesaría saber si ha encontrado algún caso natural convincente donde las estándar son realmente necesarias, y si no, si tiene un argumento convincente para mantener las estándar antemano de todos modos.$c,n_0$$c,n_0$

Prefiero enseñar la definición original con cuantificadores.

En mi opinión, los humanos generalmente tienen problemas para comprender fórmulas y definiciones con más de dos alternancias de cuantificadores directamente. La introducción de nuevos cuantificadores puede aclarar lo que significa la definición. Aquí, los dos últimos cuantificadores solo significan "para todos los n suficientemente grandes", la introducción de este tipo de cuantificación puede ayudar.

Las imágenes que dibujo para explicar estos conceptos coinciden mejor con las versiones cuantificadoras.

Creo que la simplificación del límite es útil para estudiantes de ingeniería que solo están interesados ​​en calcular la tasa de crecimiento, pero no serán tan útiles para los estudiantes de informática. De hecho, usar esta simplificación puede causar más daño que bien.

Esta idea es similar a la sugerencia de que usemos las reglas para calcular derivados (de polinomios, exponenciación, ..., regla de cadena, ...) en lugar de la definición de épsilon-delta, que en mi humilde opinión no es una buena idea.

Editar: revisión principal en la revisión 3.

Como nunca he enseñado una clase, no creo que pueda reclamar nada convincente sobre lo que deberíamos enseñar. Sin embargo, aquí está lo que pensé al respecto.

Hay ejemplos naturales en los que no se puede aplicar el "truco límite" tal como está escrito. Por ejemplo, suponga que implementa un "vector de longitud variable" (como el vector <T> en C ++) usando una matriz de longitud fija con duplicación de tamaño (es decir, cada vez que está a punto de exceder el tamaño de la matriz, usted reasignar la matriz dos veces más grande que ahora y copiar todos los elementos). El tamaño S ( n ) de la matriz cuando almacenamos n elementos en el vector es la potencia más pequeña de 2 mayor o igual que n . Queremos decir que S ( n ) = O ( n ), pero usar el "truco límite" como está escrito como definición no nos permitiría hacerlo porque S ( n) / n oscila densamente en el rango [1,2). Lo mismo se aplica a Ω () y Θ ().

Como cuestión un tanto separada, cuando usamos estas notaciones para describir la complejidad de un algoritmo, creo que su definición de Ω () a veces es inconveniente (aunque supongo que esa definición es común). Es más conveniente definir que f ( n ) = Ω ( g ( n )) si y solo si limsup f ( n ) / g ( n )> 0. Esto se debe a que algunos problemas son triviales para infinitos valores de n ( como el problema de mecanizado perfecto en un gráfico con un número impar n de vértices). Lo mismo se aplica a Θ () y ω ().

Por lo tanto, personalmente considero que las siguientes definiciones son las más convenientes para describir la complejidad de un algoritmo: para las funciones f , g : ℕ → ℝ _{> 0} ,

• f ( n ) = o ( g ( n )) si y solo si limsup f ( n ) / g ( n ) = 0. (Esto es equivalente a lim f ( n ) / g ( n ) = 0.)
• f ( n ) = O ( g ( n )) si y solo si limsup f ( n ) / g ( n ) <∞.
• f ( n ) = Θ ( g ( n )) si y solo si 0 <limsup f ( n ) / g ( n ) <∞.
• f ( n ) = Ω ( g ( n )) si y solo si limsup f ( n ) / g ( n )> 0. (Esto es equivalente a que f ( n ) no es o ( g ( n )).)
• f ( n ) = ω ( g ( n )) si y solo si limsup f ( n ) / g ( n ) = ∞. (Esto es equivalente a que f ( n ) no es O ( g ( n )).)

o equivalente,

• f ( n ) = o ( g ( n )) si y solo si para cada c > 0, para n suficientemente grande , f ( n ) ≤ c ⋅ g ( n ).
• f ( n ) = O ( g ( n )) si y solo si para algunos c > 0, para n suficientemente grande , f ( n ) ≤ c ⋅ g ( n ).
• f ( n ) = Θ ( g ( n )) si y solo si f ( n ) = O ( g ( n )) yf ( n ) = Ω ( g ( n )).
• f ( n ) = Ω ( g ( n )) si y solo si para algún d > 0, para infinitamente n , f ( n ) ≥ d ⋅ g ( n ).
• f ( n ) = ω ( g ( n )) si y solo si por cada d > 0, por infinitamente n , f ( n ) ≥ d ⋅ g ( n ).

Pero no sé si esta es una práctica común o no. Además, no sé si es adecuado para la enseñanza. El problema es que a veces queremos definir Ω () liminf en su lugar (como lo hizo en la primera definición). Por ejemplo, cuando decimos "La probabilidad de error de este algoritmo aleatorio es 2 ^{−Ω ( n )} ", ¡no queremos decir que la probabilidad de error sea exponencialmente pequeña simplemente para infinitos n !

Usar límites es un poco confuso ya que (1) es una noción más complicada (2) no captura f = O (g) muy bien (como podemos ver en la discusión anterior). Por lo general, hablo de funciones desde los números naturales (estrictamente positivos) hasta los números naturales (que son suficientes para tiempos de ejecución), omito las pequeñas cosas, y luego la definición es concisa y apropiada para los estudiantes de primer año:

Dfn: f = O (g) si para algo de C para todo n tenemos que f (n) <= C * g (n)

Cuando tomé cursos básicos, nos dieron la cosa como definición y las otras cosas como teorema.$\exists c,n_0 \dots$

Creo que el primero es más natural para muchas personas que piensan discreto en lugar de continuo, es decir, la mayoría de los informáticos (en mi experiencia). También se ajusta mejor a la forma en que generalmente hablamos de esas cosas: "Hay una función polinomial de grado 3 que es un límite superior para esta hasta un factor constante".$f$

$f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$$d=f(n_0)$

El límite es bastante útil para calcular clases de complejidad, es decir, con lápiz y papel.

En cualquier caso, creo que es muy útil que los estudiantes aprendan que hay una gran cantidad de (con suerte) definiciones equivalentes. Deberían poder darse cuenta de eso y distinguir las diferencias en caso de definiciones no equivalentes.

Habiendo estudiado estos conceptos hace solo unos años, no fueron los más difíciles de entender para mi clase (a diferencia de conceptos como inducción o contra positivos). Límites y limsups son solo más "intuitivos" para aquellos familiarizados con el cálculo en mi opinión. Pero los estudiantes con una base matemática de este tipo tendrán antecedentes teóricos establecidos de todos modos, para que puedan procesar calificadores discretos.

Además, lo que es más importante, recuerde que, en última instancia, sus alumnos continuarán (con suerte) para leer otros libros de texto de teoría de cs, y tal vez incluso algún día de investigación. Como tal, es mejor que se sientan cómodos con la notación estándar en el campo, incluso si inicialmente no se concibió idealmente. No tiene nada de malo darles definiciones alternativas también, una vez que hayan asimilado las estándar.

Para una versión interesante del tema, mire la carta bien escrita de Don Knuth "Cálculo vía notación O" . Él defiende la opinión inversa de que el cálculo debe enseñarse a través de las anotaciones 'A', 'O' y 'o'.

$x$$A$$y$$x = A(y)$$|x| \leq y$$100$$A(200)$

1. Las definiciones de Tsuyoshi Ito no se ven del todo bien. Para little-omega y big-omega, las definiciones deben usar liminf, no limsup. La definición de big-theta necesita un límite inferior en liminf y un límite superior en limsup.

2. Una definición de f (n) = O (g (n)) es que existe otra función f '(n)> = f (n) tal que lim f' (n) / g (n) <infinito.

3. ¿Por qué se permite a los novatos publicar respuestas pero no hacer comentarios?

Primero , trato de desarrollar en los estudiantes cierta intuición , antes de mostrar ecuaciones.

• "Combinar-ordenar vs Insertar-Ordenar" es un buen punto de partida.

Otro aspecto es que depende en gran medida del programa de estudios concretos. En mi humilde opinión, dependiendo de los temas anteriores, una de las definiciones será más adecuada, mientras que en mi humilde opinión, es una buena idea mostrar ambos y aceptar ambos tipos de soluciones.