Cómo resolver problemas sobre el análisis de algoritmos paso a paso

Estos problemas son preguntas simples como las que se harían en una tarea. A lo que le preguntaría al interrogador, como le preguntaría a mi hija estudiante de secundaria, “¿sabes lo que significa cuadrático?” Si la respuesta a eso fuera satisfactoria, preguntaría, “¿sabes cómo resolver problemas de razón?”. Si puede responder satisfactoriamente a mis dos preguntas, entonces la respuesta a esos dos problemas es trivial. El hecho de que ambos problemas dependan de los mismos dos conceptos sugiere que son problemas de tarea diseñados para que el alumno comprenda y use esos conceptos. Nadie más puede aprender por usted, necesita aprender usted mismo.

Estas son las dos cosas que debería haber aprendido: “cuadrático” significa involucrar el cuadrado de algo, x veces x es x al cuadrado y es cuadrático en x.

Y, así es como se configura un problema de razón x es a y como z es a lo que está escrito: x / y = z / what y puedes resolverlo con un álgebra simple what = y / (x * z). ¿Eso es encontrar lo que tomas y y dividirlo por x y dividirlo por z? Dejaré el álgebra si el orden de z y lo que se invierte.

Ahora, si su problema es cuadrático en los numeradores (x y z), entonces el problema es qué = y / (x * x * z * z), si son los denominadores los que son cuadráticos qué * qué = (y * y ) / (x * z), y tomando la raíz cuadrada de ambos lados: what = y / sqrt (x * z).

Todo lo que tiene que hacer es descubrir cómo los números en su problema se mapean en x, y y z y usar el problema de razón apropiado, cuadrando los números correctos y luego, por supuesto, resolviendo. Cuando lo haga, creo que encontrará que los problemas tienen respuestas sorprendentemente simples, uno involucra un factor de cuatro, el otro un factor de dieciséis.

Determinar el tiempo de ejecución de un algoritmo sobre varios conjuntos de problemas es una cuestión de conocer la complejidad de tiempo del algoritmo (tiempo cuadrático, en el caso de sus ejemplos) y el tamaño relativo de los conjuntos de problemas. Así es como puede determinar esto:

  1. Basado en la tabla de complejidades de tiempo comunes en esta página, puede determinar cuál es la fórmula apropiada para la complejidad de tiempo de una ecuación cuadrática: Complejidad de tiempo
  2. Luego, toma el nuevo tamaño de entrada y lo divide por el tamaño de entrada original. Esta relación es cuánto está cambiando el espacio del problema, siendo 1 sin cambio.
  3. Pones este valor en el término apropiado en la tabla. Para hacer esto, elimine el O () y use el resto (por ejemplo, O (n log n) ==> n log n), reemplazando n con la proporción que obtuvo en el paso 2. Este valor es el tiempo que tomará resolver el nuevo conjunto de problemas proporcionalmente al conjunto original. 1 = al mismo tiempo, 2 = doble, etc.
  4. Luego multiplica este resultado por tu tiempo original. Esto le da el tiempo total que el nuevo conjunto de problemas debería tomar para resolver.

Aquí hay un ejemplo:
“Un algoritmo tarda 7 segundos en resolver un problema de tamaño 50. Si el algoritmo es cúbico, ¿cuánto tiempo llevará resolver un problema de tamaño 75?”

  1. En la página anterior, vemos que la fórmula para el tiempo cúbico es O ( n ^ 3 )
  2. Nuestro nuevo conjunto de problemas es (75/50 = 1.5) veces el tamaño del conjunto de problemas original.
  3. O (n ^ 3) ==> n ^ 3 ==> 1.5 ^ 3 ==> 3.375
  4. Tiempo original = 7 segundos, * 3.375 = 23.625 segundos

Eso debería darle la información que necesita para resolver los problemas en su pregunta.

Como dijo Anwesh, sin embargo, para el primero puede usar una actitud más simple
5 segundos para el tamaño de entrada de 100, el algoritmo es cuadrático, por lo que si la entrada es el doble del tamaño = 200, el tiempo será size_icr ^ complejidad = 2 ^ 2 = 4 veces más largo -> 5 * 4 = 20 s

Cuadrático significa que depende del cuadrado del tamaño de entrada. Entonces, si lleva 5 segundos resolver una entrada de longitud 100, tomará 20 segundos resolver una entrada de longitud 200.

Tiempo final = 5 * 200 * 200 / (100 * 100)

Se puede usar la misma analogía para la segunda parte