Cómo entender rápidamente la complejidad del tiempo en su conjunto y sus 3 anotaciones

Cuando comparamos dos algoritmos, idealmente nos gustaría saber sus tiempos de ejecución para decir cuál de ellos es mejor. Pero obviamente no podemos medirlo en todas las entradas, por lo que necesitamos una noción simplificada para usar en lugar del tiempo de ejecución. Si no podemos medir el tiempo, nuevamente, idealmente, nos gustaría decir “este algoritmo cuando se ejecuta en entradas de tamaño n no realiza más de 17 * n ^ 2 + 132 * n + 46 operaciones” y luego podemos compararlo con cualquier otro, pero obviamente nadie quiere contar las instrucciones y, lo que es más importante, el número de instrucciones depende en gran medida de las optimizaciones que no son de naturaleza algorítmica, por lo que no deben tenerse en cuenta al comparar las eficiencias de los algoritmos.

Entonces, la solución es decidir que sí, si n es pequeño, entonces 132 * n puede ser más importante para el tiempo de ejecución del programa que 17 * n ^ 2, pero solo para los pequeños, si suponemos que n puede ser arbitrariamente grande para Casi todos los valores posibles de n 132 * n son completamente insignificantes en comparación con 17 * n ^ 2. Y si es 17 o 34 también es insignificante, significa que el tiempo de ejecución será 2 veces más largo, pero si n es muy grande que 2 veces es tan pequeño en comparación con n ^ 2 que podemos decir que corre proporcionalmente a n ^ 2 es la única información importante: si alguien propone un algoritmo que sea algo mejor que n ^ 2, no importará en absoluto que tal vez nuestro tenga este tiempo 2 veces más corto o más largo, porque su algoritmo será mejor de forma arbitraria factor grande (si n es arbitrariamente grande). Por supuesto, esos no necesitan ser elementos polinómicos, pueden ser funciones como n log n, etc., pero siempre nos olvidamos de todos los elementos, aparte del que crece más rápidamente cuando n tiende al infinito, así como también sobre el constantes

Esto no es ideal, por supuesto, porque en el mundo real nunca haremos cálculos sobre valores arbitrariamente grandes (“n

(Esto es complejidad de tiempo, tal vez solo una cosa que valga la pena especificar es qué era “n” después de todo. En las definiciones formales y, por ejemplo, cuando asignamos los algoritmos a las clases de complejidad, es el número de bits de la entrada. En la práctica, a menudo es un es un poco desagradable usar una definición tan estricta, por lo que en la práctica n puede ser lo que acordamos, por ejemplo, si la entrada es una secuencia de números, usaremos el número como n. Lo único importante es que todos sepan lo que acordado como n en un caso específico y luego, si alguien realmente necesita pensar en la cantidad de bits, puede hacer la transición ellos mismos, pero generalmente no es necesario).

La forma en que lo expliqué era grande-Theta, es decir, el tiempo de ejecución es proporcional a n ^ 2 – para nuestra función f (n) = 17 * n ^ 2 + 132 * n + 46 es cierto que para valores suficientemente grandes de n 17 * n ^ 2

El segundo concepto es la complejidad del peor de los casos, el caso promedio y el mejor de los casos, que es completamente independiente de O, Omega y Theta (lo siento, Artur Chakhvadze, pero su explicación que vincula a Theta con el peor y el mejor de los casos es incorrecta. Las 9 posibilidades son perfectamente bien, como ejemplo, la búsqueda binaria tiene la complejidad del caso más desfavorable y del caso medio [math] \ Theta (log n) [/ math] y la complejidad del mejor caso [math] \ Theta (1) [/ math]). Si alguien solo habla de complejidad, por defecto significan el peor de los casos, es decir, si la complejidad es [matemática] \ Theta (n ^ 2) [/ matemática] entonces para la entrada que toma más tiempo de todos los posibles de tamaño n el algoritmo tomará n ^ 2. El caso promedio describe el tiempo promedio sobre todas las entradas de tamaño n, muy a menudo es lo mismo que el peor de los casos, pero a menudo no lo es y, en tales casos, es la decisión de cualquier persona que use el algoritmo en la práctica al final decidir si El uso individual del caso peor o promedio es más importante, a menudo es promedio. La tercera noción es el mejor caso y es bastante inútil (aparte de los casos, podemos derivar algunas afirmaciones más sofisticadas al respecto, de modo que el mejor caso se aplica a un conjunto específico de entradas que por alguna razón consideramos importantes).

La complejidad temporal del algoritmo es una medida de cómo el tiempo de cálculo depende del tamaño de su problema.

Por ejemplo, considere el problema de encontrar la posición de un elemento en particular en una matriz sin clasificar. Para resolverlo, seleccionará elementos de la matriz en bucle hasta que seleccione el elemento deseado o llegue al final. Es fácil ver que, en el peor de los casos, si su elemento es el último elemento de la matriz, la cantidad de operaciones que debe realizar es proporcional al tamaño de su matriz. Por lo tanto, la complejidad del peor de los casos de su algoritmo es [matemática] O (n) [/ matemática] (pronunciada “Gran O de n”) donde [matemática] n [/ matemática] es el número de elementos. Aquí Big-O es una forma corta de decir que existen algunas [matemáticas] c [/ matemáticas] constantes, como por ejemplo para cualquier conjunto de tamaño [matemáticas] n [/ matemáticas], (estrictamente hablando, lo suficientemente grande [matemáticas] n [/ math]) el tiempo de cálculo no excederá [math] c \ cdot n [/ math] segundos.

Ahora suponga que su matriz está ordenada. Luego puede usar la búsqueda binaria: tome el elemento del medio, compárelo con un elemento que está tratando de encontrar y, dependiendo de si es más pequeño, mayor o igual, repita el procedimiento para la mitad izquierda o derecha de la matriz, o detener. Se puede demostrar que la peor complejidad de la búsqueda binaria es [matemática] O (\ log n) [/ matemática] porque después de cada iteración está resolviendo el problema dos veces más pequeño que el original, y para una matriz de tamaño [matemática] 2 ^ k [/ math] su tiempo de ejecución será proporcional a [math] k [/ math].

En ambos ejemplos puede suceder que encuentre el elemento deseado después de la primera iteración. Lo que significa que la mejor complejidad de caso es [matemática] O (1) [/ matemática]. Pero si tiene que calcular el número de ocurrencias de algún elemento en una matriz no ordenada, siempre debe iterar a través de una secuencia completa, por lo que el tiempo de ejecución siempre será proporcional a su longitud. En este caso, la complejidad del algoritmo se denota [math] \ Theta (n) [/ math] (pronunciado “Big Theta of n”) donde theta significa que la peor complejidad del algoritmo es igual a su mejor complejidad de caso.

También existen pocas anotaciones más, por ejemplo, [matemática] o (f (n)) [/ matemática] significa que por cada [matemática] c [/ matemática] fija existe lo suficientemente grande [matemática] n [/ matemática] como para que su algoritmo resolverá cualquier problema de tamaño [matemática] n [/ matemática] en menos de [matemática] c \ cdot f (n) [/ matemática] segundos. Pero no se usan con mucha frecuencia.