[Powered by Google Translate] Usted probablemente ha oído hablar de un algoritmo rápido o eficiente para la ejecución de su tarea en particular, pero ¿qué significa esto para un algoritmo para ser rápido o eficiente? Bueno, no está hablando de una medición en tiempo real, como segundos o minutos. Esto se debe a hardware informático y puede variar drásticamente. Mi programa puede correr más lento que el tuyo, porque lo estoy corriendo en un ordenador antiguo, o porque se me ocurre estar jugando un juego de video en línea al mismo tiempo, que está acaparando todo mi memoria, o podría estar corriendo mi programa a través de diferentes programas que se comunica con la máquina de manera diferente en un nivel bajo. Es como comparar manzanas y naranjas. El hecho de que mi equipo más lento tarda más que el tuyo para devolver una respuesta no significa que usted tiene el algoritmo más eficiente. 

Por lo tanto, ya que no se puede comparar directamente los tiempos de ejecución de los programas en cuestión de segundos o minutos, ¿Cómo podemos comparar dos algoritmos diferentes independientemente de su hardware o el entorno del software? Para crear una forma más uniforme de medición de la eficiencia algorítmica, los informáticos y matemáticos han ideado conceptos para la medición de la complejidad asintótica de un programa y una notación llamada "Ohnotation Big ' para describir esto. La definición formal es que una función f (x) se ejecuta en el orden de g (x) si existe algún valor (x), x ₀ y alguna constante C, para lo cual f (x) es menor que o igual a esa constante g veces (x) para todo x mayor que x ₀. 

Pero no se asustan por la definición formal. ¿Qué significa esto en realidad significa en términos menos teóricos? Bueno, es básicamente una forma de analizar la rapidez de ejecución de un programa crece asintóticamente. Es decir, como el tamaño de los insumos aumenta hacia el infinito, Oye, estás ordenar una matriz de tamaño 1000 en comparación con una matriz de tamaño 10. ¿Cómo afecta el tiempo de ejecución de su programa de crecer? Por ejemplo, imaginar contando el número de caracteres en una cadena de la forma más sencilla  caminando a través de toda la cadena letra por letra y añadiendo 1 a un contador para cada carácter. Este algoritmo se dice que se ejecutan en tiempo lineal con respecto al número de caracteres, 'N' en la cadena. En resumen, se ejecuta en O (n). ¿Por qué es esto? Así, con este método, el tiempo requerido para atravesar la cadena completa es proporcional al número de caracteres. Contar el número de caracteres de una cadena de 20 caracteres se va a tomar el doble de tiempo que sea necesario para contar los caracteres de una cadena de 10 caracteres, porque hay que mirar a todos los personajes y cada personaje tiene la misma cantidad de tiempo para mirar. A medida que aumenta el número de caracteres, el tiempo de ejecución se incrementará linealmente con la longitud de entrada. 

Ahora, imagínese si usted decide que el tiempo lineal, O (n), simplemente no era lo suficientemente rápido para ti? Tal vez usted está almacenando enormes cadenas, y usted no puede pagar el tiempo extra que tendría para recorrer la totalidad de sus caracteres de conteo uno por uno. Por lo tanto, usted decide intentar algo diferente. ¿Qué pasaría si a almacenar ya el número de caracteres en la cadena, por ejemplo, en una variable llamada 'len' desde el principio en el programa, incluso antes de almacenar el primer carácter en la cadena? Entonces, lo único que tendría que hacer ahora para averiguar la longitud de la cadena, es comprobar cuál es el valor de la variable es. Usted no tiene que mirar la propia cadena en absoluto, y acceder al valor de una variable como len se considera un tiempo asintóticamente constante operación, o O (1). ¿Por qué es esto? Bueno, ¿recuerdas lo que significa complejidad asintótica. ¿Cómo cambia el tiempo de ejecución como el tamaño de sus entradas crece? 

Digamos que se trata de conseguir el número de caracteres de una cadena más grande. Bueno, no importa lo grande que hacer la cadena, hasta un millón de caracteres de longitud, Todo lo que tienes que hacer para encontrar la longitud de la cuerda con este enfoque, es leer el valor de la len variable, que ya ha hecho. La longitud de la entrada, es decir, la longitud de la cadena que se está tratando de encontrar, no afecta en absoluto la velocidad de su programa se ejecuta. Esta parte de su programa funcionaría igual de rápido en una cadena de un solo carácter y una cadena de mil caracteres, y es por eso que este programa se denomina ejecución en tiempo constante con respecto al tamaño de la entrada. 

Por supuesto, hay un inconveniente. Te pasas el espacio de memoria adicional en su ordenador almacenar la variable y el tiempo extra que le lleva para hacer el almacenamiento real de la variable, pero el punto sigue en pie, averiguar cuánto tiempo la cadena se no depende de la longitud de la cadena en absoluto. Así, se ejecuta en O (1) o constante de tiempo. Esto ciertamente no tiene por qué significar que el código se ejecuta en un paso, pero no importa la cantidad de pasos que es, Si no cambia con el tamaño de las entradas, aún así es asintóticamente constante que representamos como O (1). 

Como podrán imaginar, hay muchos diferentes tiempos de ejecución Big O para medir con algoritmos. O (n) ² algoritmos son asintóticamente más lento que O (n) algoritmos. Es decir, como el número de elementos (n) crece, con el tiempo O (n) ² algoritmos tomará más tiempo de O (n) algoritmos para correr. Esto no significa que O (n) algoritmos siempre se ejecutan más rápido de O (n) ² algoritmos, incluso en el mismo entorno, en el mismo hardware. Tal vez para pequeños tamaños de entrada,  el O (n) ² algoritmo podría funcionar más rápido, pero, con el tiempo, ya que el tamaño de entrada aumenta hacia el infinito, el O (n) tiempo de ejecución del algoritmo ² finalmente eclipsará el tiempo de ejecución de la O (n) algoritmo. Al igual que cualquier función matemática de segundo grado  eventualmente superará a cualquier función lineal, no importa la cantidad de un cabezal de iniciar la función lineal comienza con. Si está trabajando con grandes cantidades de datos, algoritmos que se ejecutan en O (n) ² realmente puede llegar a ralentizar su programa, pero para tamaños pequeños de entrada, probablemente ni siquiera se dará cuenta. 

Otra complejidad asintótica es, tiempo logarítmica, O (log n). Un ejemplo de un algoritmo que se ejecuta este rápidamente es el algoritmo de búsqueda binaria clásica, para buscar un elemento en una lista ya-ordenados de elementos. 

Si usted no sabe lo que hace la búsqueda binaria, Te lo explicaré para que usted realmente rápido. Digamos que usted está buscando el número 3 en esta matriz de enteros. Se ve en el elemento central de la matriz y pregunta: "¿Está el elemento que quiero mayor, igual o menor que esto?" Si es igual, entonces genial. Usted encontró el elemento, y ya está. Si es mayor, entonces usted sabe que el elemento tiene que estar en el lado derecho de la matriz, y sólo se puede observar que, en el futuro, y si es menor, entonces usted sabe que tiene que estar en el lado izquierdo. Este proceso se repite entonces con la matriz de menor tamaño hasta que el elemento se encuentra el correcto. 

Esta potente algoritmo reduce el tamaño de la matriz a la mitad con cada operación. Por lo tanto, para encontrar un elemento en una matriz ordenada de tamaño 8, en la mayoría (log ₂ 8), o 3 de estas operaciones, comprobando el elemento medio, entonces el corte de la matriz en un medio se requerirá, mientras que una matriz de tamaño 16 tiene (log ₂ 16), o 4 operaciones. Eso es sólo una operación más por una serie duplicado en tamaño. Doblando el tamaño de la matriz aumenta el tiempo de ejecución sólo en un 1 trozo de este código. Una vez más, comprobar el elemento central de la lista, y luego partir. Así, se dice que opera en tiempo logarítmico, O (log n). Pero espere, usted dice, ¿esto no dependen del lugar en la lista el elemento que está buscando es? ¿Y si el primer elemento se mire resulta ser la correcta? Entonces, sólo se necesita una operación, no importa qué tan grande es la lista. 

Bueno, es por eso que los informáticos tienen términos más la complejidad asintótica que reflejan el mejor de los casos y en el peor de los casos actuaciones de un algoritmo. Más adecuadamente, los límites superior e inferior en el tiempo de ejecución. En el mejor de los casos para la búsqueda binaria, es nuestro elemento justo en el medio, y usted lo consigue en tiempo constante, no importa lo grande que el resto de la matriz es. El símbolo utilizado para esto es Ω. Por lo tanto, este algoritmo se dice que ejecutar en Ω (1). En el mejor de los casos, se encuentra el elemento rápidamente, no importa qué tan grande es la matriz, pero en el peor de los casos, que tiene que realizar (log n) los controles parciales de la matriz para encontrar el elemento correcto. Límites peor de los casos superiores se denominan con la gran "O" que usted ya sabe. Por lo tanto, es O (log n), pero Ω (1). 

Una búsqueda lineal, por el contrario, en el que a través de cada elemento de la matriz para encontrar el que usted desea, es en el mejor de Ω (1). Una vez más, el primer elemento que desee. Por lo tanto, no importa qué tan grande es la matriz. En el peor caso, que es el último elemento de la matriz. Por lo tanto, tienes que caminar a través de todos los n elementos de la matriz para encontrarlo, como si estuviera buscando un 3. Por lo tanto, se ejecuta en O (n) tiempo porque es proporcional al número de elementos de la matriz. 

Un símbolo más utilizado es Θ. Esto puede ser usado para describir los algoritmos donde los casos mejor y peor son los mismos. Este es el caso de los algoritmos de longitud de cadena que hablamos antes. Es decir, si la almacenamos en una variable antes almacenamos la cadena y acceder a ella más tarde en tiempo constante. No importa qué número estamos almacenando en esa variable, vamos a tener que mirarlo. El caso es que mire y encontrar la longitud de la cadena. Así Ω (1) o en el mejor de los casos la constante de tiempo. El peor caso es, nos fijamos en ella y encontrar la longitud de la cadena. Así, O (1) o constante de tiempo en el peor caso. Así, dado que la mejor y el peor de los casos son los mismos, esto se puede decir para funcionar en Θ (1) hora. 

En resumen, tenemos una buena manera de razonar acerca de los códigos de eficiencia sin saber nada sobre el tiempo real que tarda en ejecutarse, que se ve afectada por muchos factores externos, incluyendo hardware diferentes, software, o los detalles de su código. Además, nos permite razonar bien sobre lo que sucederá cuando el tamaño de los incrementos de los insumos. 

Si ejecuta en O (n) ² algoritmo, o peor aún, un O (2 ⁿ) algoritmo, uno de los más rápidos tipos de cultivo, que realmente va a empezar a notar la desaceleración cuando empiezas a trabajar con grandes cantidades de datos. 

Esa es la complejidad asintótica. Gracias.