Cuando se discute un algoritmo, el uso común del símbolo [math] T [/ math] es representar su complejidad temporal.
[matemáticas] T [/ matemáticas] es una función . La entrada a esta función es el tamaño de entrada , la salida es el tiempo de ejecución (en el peor de los casos) para una entrada de ese tamaño.
Por lo tanto, [math] T (n) [/ math] es un número : el número devuelto por la función [math] T [/ math] cuando se le da el número [math] n [/ math]. Este número es el tiempo de ejecución de nuestro algoritmo en una entrada de tamaño [math] n [/ math].
- Matemática discreta: ¿Cuál es la diferencia entre ser un elemento de un conjunto o ser un subconjunto de un conjunto?
- ¿Es P vs NP el problema más difícil e importante del Premio del Milenio?
- ¿Ser bueno en matemáticas ayuda en la programación?
- Cómo responder a las consultas de rango medio de manera eficiente
- ¿Qué se usó antes de LaTeX para escribir documentos matemáticos? ¿Cómo se dibujaron las figuras? ¿Cómo se generaron y posicionaron las ecuaciones matemáticas con notación complicada en el documento? ¿Quién hizo la composición en su forma final para imprimir después de que fue aceptada?
La [matemática] O [/ matemática] en “[matemática] O (n) [/ matemática]” no es una función . Esta es la notación Big O. En particular, el símbolo [math] O (n) [/ math] representa la clase de todas las funciones que crecen (asintóticamente) como máximo tan rápidamente como la función lineal [math] f (n) = n [/ math].
La notación Big O nos brinda una forma conveniente de hablar sobre los límites superiores. Por ejemplo, podemos decir “la complejidad temporal de este algoritmo es [matemática] O (n ^ 2) [/ matemática]” (formalmente: “[matemática] T \ en O (n ^ 2) [/ matemática]”) decir que el tiempo de ejecución del algoritmo es como máximo cuadrático en el tamaño de entrada.
A veces, puede ver que ambos símbolos se usan en una sola ecuación. Por ejemplo, la complejidad temporal de MergeSort se describe comúnmente por la siguiente recurrencia: “[matemáticas] T (n) = 2T (n / 2) + O (n) [/ matemáticas]”.
El significado de la declaración anterior: para cualquier [matemática] n [/ matemática], el tiempo [matemático] T (n) [/ matemático] necesario para ordenar los elementos [matemáticos] n [/ matemático] puede calcularse tomando el tiempo [math] T (n / 2) [/ math] necesitaba clasificar los elementos [math] n / 2 [/ math], multiplicando ese tiempo por 2 y agregando algo extra. Ese algo extra debe ser como máximo lineal en [math] n [/ math].
