¿Puedes explicar cómo calcular las complejidades temporales de los algoritmos con un ejemplo?

Answer 1

La forma en que realice su análisis variará de un algoritmo a otro y qué modelo de cálculo adoptará. Por ejemplo, la técnica descrita por Priyanshu funciona mejor para los algoritmos Divide and Conquer, donde un algoritmo se describe de forma recursiva. Desea contar la cantidad de pasos realizados según el tipo de caso que esté buscando. Antes de nada, debe determinar el tamaño de entrada de su problema, por simplicidad aquí, asumiré que el tamaño de entrada se denota por [math] n [/ math]. Normalmente observamos la peor situación: estas son instancias en las que el algoritmo realiza la mayor cantidad de pasos con respecto al tamaño de entrada. Algunos algoritmos tienen situaciones específicas del peor de los casos, otros puede ser el caso de que cada instancia sea una de las peores. Identifique uno de estos casos.

Daré un ejemplo básico. La clave que desea identificar en el algoritmo es lo que a veces se denomina un buen barómetro. Un barómetro es una línea en el pseudocódigo de un algoritmo (suponiendo que lo tenga, si no es que identifica el paso del algoritmo que tiene esta propiedad) que se ejecuta con tanta frecuencia como cualquier otra línea en el pseudocódigo. Por ejemplo, en un algoritmo de ordenación basado en comparación, este es normalmente el número de intercambios.

A continuación, lo que debe hacer es formular una función que modele la cantidad de veces que se ejecuta el barómetro. Intente encontrar una forma cerrada para su función, luego determine su complejidad. Esto se hace al encontrar una función de crecimiento a la que pertenece su función en términos de decir Big-Oh o Big-Theta. Una vez que haga esto, debe hacerse dos preguntas:

1. ¿Es mi análisis estricto? Es decir, ¿puedo encontrar un mejor resultado asintótico?
2. Mirando mi algoritmo, ¿hay algún lugar donde pueda mejorar la complejidad del tiempo de un paso importante para mejorar su eficiencia general?

Analicemos esto usando un ejemplo simple: InsertionSort (tenga en cuenta que este pseudocódigo no es la única forma de escribir el algoritmo, pero su corrección no es importante para esta discusión, solo se trata de la complejidad del tiempo).

1. ¿Cuál es el tamaño de entrada? Es la longitud de la matriz, [math] n [/ math].
2. ¿Cuál es el peor caso aquí? Una matriz dada en orden inverso (p. Ej., [7,6,5,4,3,2,1])
3. Ahora necesitamos identificar un buen barómetro. ¿Qué línea funciona? Aquí cualquiera de 7,8,9 haría el truco (tenga en cuenta que 7 tiene que hacer una verificación adicional antes de determinar abandonar la estructura del bucle while). Vamos a elegir la línea 8.
4. Observe que en la línea 6, j = i-1, y (i-1) se producen intercambios en cada iteración del bucle (línea 4). Entonces formulamos nuestra suma que cuenta el número de veces que la línea 8 ocurre como: [math] \ sum_ {i = 2} ^ {n} {(i-1)} [/ math]
5. Ahora tenemos que encontrar una forma cerrada, así que simplificamos la suma anterior: [matemáticas] \ sum_ {i = 2} ^ {n} {(i-1)} = \ sum_ {i = 2} ^ {n} { i} – \ sum_ {i = 2} ^ {n} {1} = {n (n + 1) \ over 2} – 1 – (n-2 + 1) = {n ^ 2 + n – 2n \ over 2} = {n (n-1) \ over 2}. [/ Math]
6. Ahora descubrimos la complejidad temporal del algoritmo usando la forma cerrada. Bueno, aquí no es demasiado difícil ver que [matemáticas] n ^ 2 [/ matemáticas] domina la fórmula de forma cerrada que derivamos. Entonces, demostremos [math] {n (n-1) \ over 2} \ en O (n ^ 2) [/ math]. Esto lo dejaré como un ejercicio para probar (puede aplicar el Teorema del límite para Big Oh, o la definición directamente).

También le animo a que también revise esta pregunta, está relacionada con la suya: ¿Cuáles son algunas formas fáciles de comprender y calcular la complejidad temporal de los algoritmos?

¡Espero que esto ayude!

Answer 2

Debería encontrar una relación de recurrencia generalizada para el algoritmo (siempre que sea posible). Esto se puede hacer una vez que comprenda el algoritmo. Consejo: intente expresar la solución al problema como el resultado compuesto de los subproblemas subyacentes.
Entonces puede usar uno de los tres métodos para encontrar la complejidad, como se enseña aquí.