¿Cómo encuentro el tiempo de ejecución dado la velocidad del algoritmo y la velocidad de la computadora?

Question

Actualmente estoy trabajando en una tarea que trata con Big-O y los tiempos de ejecución. Tengo una pregunta que me ha sido presentada que parece ser muy fácil, pero no estoy seguro de si lo estoy haciendo correctamente. El resto de los problemas han sido bastante difíciles, y siento que estoy pasando por alto algo aquí.

Primero, tienes estas cosas: El algoritmo A, que tiene un tiempo de ejecución de 50n ^ 3. La computadora A, que tiene una velocidad de 1 milisegundo por operación. Computadora B, que tiene una velocidad de 2 milisegundos por operación. Una instancia de tamaño 300.

Quiero saber cuánto tiempo lleva el algoritmo A para resolver esta instancia en la computadora A y cuánto tiempo tarda en la computadora B.

Lo que quiero hacer es sub 300 in para n, así que tienes 50 * (300 ^ 2) = 4500000.

Luego, multiplica eso por 1 para la primera computadora, y por 2 para la segunda computadora.

Esto me resulta extraño, sin embargo, porque dice que " tiempo de ejecución " es 50n ^ 3, no, " el número de operaciones es 50n ^ 3 " ;, así que tengo la sensación de que estoy multiplicando el tiempo por el tiempo, y terminaría con unidades de milisegundos al cuadrado, lo que no parece correcto todos.

Me gustaría saber si tengo razón, y si no, qué significa realmente la pregunta.

Answer 1

No tendría sentido si tuviera O (n ^ 3) pero no está usando la notación O grande en su ejemplo. Es decir. si tuviera O (n ^ 3) sabría la complejidad de su algoritmo pero no sabría el número exacto de operaciones como dijo.

En su lugar, parece que se le da el número exacto de operaciones que se realizan. (Incluso saber que no está explícitamente establecido). Así que sustituir por n tendría sentido.

La notación Big O describe cómo el tamaño de la entrada afectaría su tiempo de ejecución o el uso de la memoria. Pero con Big O no se puede deducir un tiempo de ejecución exacto, incluso dada la velocidad de cada operación.

Poner una explicación de por qué su respuesta parece tan simple (como lo describí anteriormente) también sería una forma segura. Pero estoy seguro de que incluso sin eso obtendrás las marcas de la pregunta.

Answer 2

Bueno, aparte de la inutilidad de averiguar cuánto tardará algo en las computadoras modernas, aunque podría tener un significado de algo en un sistema integrado, me parece correcto. Cómo lo hiciste.

Si el algoritmo necesita 50n ^ 3 operaciones para completar algo, donde n es el número de elementos a procesar, entonces sustituir 300 por n le dará el número de operaciones a realizar, no una unidad de tiempo.

Así que multiplica con el tiempo por operación y obtendrás el tiempo necesario.

Me parece correcto.

Answer 3

Sus datos de 50 * n ^ 3 se denominan "tiempo de ejecución", pero eso se debe a que el modelo utilizado para las evaluaciones de velocidad asume una máquina con varias operaciones básicas, donde cada una de ellas toma 1 unidad de tiempo.

En su caso, la ejecución del algoritmo toma 50 * 500 ^ 3 unidades de tiempo. En la computadora A, cada unidad de tiempo es de 1 ms, y en la computadora B de 2 ms.

Espero que esto ponga algo de sentido en las unidades,
Asaf.