algorithm - salvador - strassen multiplicación de matrices

¿Cómo podemos modificar casi cualquier algoritmo para tener un buen mejor tiempo de ejecución?

Question

Esta es una pregunta de Introduction to Algorithms By Cormen. Pero esto no es un problema de tarea en lugar de autoestudio.

He pensado mucho y busqué en google. La respuesta que se me ocurre es:

• Usa otro algoritmo.
• Déle las mejores entradas de caso
• Usa una mejor computadora para ejecutar el algoritmo.

Pero no creo que esto sea correcto. Cambiar el algoritmo no es lo mismo que hacer que un algoritmo tenga un mejor rendimiento. También usar una mejor computadora puede aumentar la velocidad pero el algoritmo no es mejor. Esta es una pregunta al principio del libro, así que creo que esto es algo simple que estoy pasando por alto.

Entonces, ¿cómo podemos modificar casi cualquier algoritmo para tener un buen mejor tiempo de ejecución?

Answer 1

Algunas veces podemos usar un algoritmo aleatorio, que hace elecciones aleatorias, para permitir un análisis probabilístico y así mejorar el tiempo de ejecución.

Answer 2

Si pudiéramos introducir una instrucción para ese mismo algoritmo en el modelo de cálculo del propio sistema, solo podemos resolver el problema en una instrucción.

Pero como es posible que ya hayas descubierto que es un enfoque muy poco realista. Por lo tanto, un método genérico para modificar cualquier algoritmo para tener un mejor tiempo de ejecución del caso es casi imposible. Lo que podemos hacer en max es aplicar ajustes en el algoritmo para las redundancias generales que se encuentran en varios problemas.

O puedes ir ingenuo tomando las mejores entradas de casos. Pero, de nuevo, eso no es realmente modificar el algoritmo. De hecho, introducir el algoritmo en el sistema de computación en sí, en lugar de ser muy poco realista, tampoco es una modificación del algoritmo.

Answer 3

Las formas en que podemos modificar el algoritmo para tener un mejor tiempo de ejecución de caso son:

• Si el algoritmo está en el punto de su propósito / solución, por ejemplo, para una ordenación creciente, ya está ordenado en orden ascendente y así sucesivamente.
• Si modificamos el algoritmo de modo que solo enviemos y salgamos para su propósito, por lo que forzamos que múltiples bucles anidados sean solo uno

Answer 4

Puede modificar cualquier algoritmo para tener una complejidad en el mejor de los casos de O(n) agregando un caso especial, que si la entrada coincide con este caso especial, devuelva una respuesta codificada en caché (o alguna otra respuesta fácil de obtener).

Por ejemplo, para cualquier tipo, puede hacer el mejor caso O(n) comprobando si la matriz ya está ordenada, y si lo está, devuélvala como está.

Tenga en cuenta que no afecta a los casos promedio ni a los peores (suponiendo que no sean mejores que O(n) ) y que, básicamente, se mejora la complejidad en el mejor tiempo del caso del algoritmo.

Nota: Si el tamaño de la entrada es limitado, la misma optimización es el mejor caso O(1) , porque la lectura de la entrada en este caso es O(1) .