Comment trouver le temps d'exécution en fonction de la vitesse de l'algorithme et de la vitesse de l'ordinateur?

Question

Je travaille actuellement sur une mission qui traite du Big-O et des temps d'exécution. Je me suis posé cette question qui semble être très facile, mais je ne suis pas sûre de le faire correctement. Le reste des problèmes a été assez difficile et je sens que je néglige quelque chose ici.

Tout d'abord, vous avez les éléments suivants: L'algorithme A, qui a une durée d'exécution de 50n ^ 3. Ordinateur A, qui a une vitesse de 1 milliseconde par opération. Ordinateur B, qui a une vitesse de 2 millisecondes par opération. Une instance de taille 300.

Je veux savoir combien de temps il faut à l'algorithme A pour résoudre cette instance sur l'ordinateur A et combien de temps cela prend pour l'ordinateur B.

Ce que je veux faire est un sous-marin de 300 po pour n, vous avez donc 50 * (300 ^ 2) = 4500000.

Ensuite, multipliez cela par 1 pour le premier ordinateur et par 2 pour le deuxième ordinateur.

Cela me semble étrange, cependant, car il indique le "temps de fonctionnement". est 50n ^ 3, non, "le nombre d'opérations est 50n ^ 3", alors j'ai l'impression que je multiplie le temps, et que je finirais avec des unités de millisecondes au carré, ce qui ne semble pas juste tous.

Je voudrais savoir si j'ai raison et, dans le cas contraire, en quoi consiste la question.

Answer 1

Cela n'aurait aucun sens si vous aviez O (n ^ 3) mais vous n'utilisez pas la grande notation O dans votre exemple. C'est à dire. si vous aviez O (n ^ 3), vous sauriez la complexité de votre algorithme mais vous ne sauriez pas le nombre exact d'opérations comme vous l'avez dit.

Au lieu de cela, il semble que le nombre exact d’opérations effectuées vous est donné. (Même sachez que ce n'est pas explicitement indiqué). Donc, substituer n serait logique.

La notation Big O décrit l’impact de la taille de l’entrée sur votre temps d’exécution ou votre utilisation de la mémoire. Mais avec Big O, vous ne pouvez pas déduire une durée de fonctionnement exacte, même compte tenu de la rapidité de chaque opération.

Expliquer pourquoi votre réponse a l'air si simple (comme je l'ai décrit ci-dessus) constituerait également un moyen sûr. Mais je suis sûr que même sans cela, vous aurez les points pour la question.

Answer 2

Eh bien, mis à part l'inutilité de déterminer combien de temps cela durera longtemps sur la plupart des ordinateurs modernes, bien que cela puisse donner un sens à un sens dans un système embarqué, il me semble évident comme vous l'avez fait.

Si l'algorithme nécessite 50n ^ 3 opérations pour effectuer quelque chose, où n est le nombre d'éléments à traiter, le remplacement de 300 par n vous donnera le nombre d'opérations à effectuer, et non une unité de temps.

Donc, multipliez le temps par opération et vous obtiendrez le temps nécessaire.

Cela me semble correct.

Answer 3

Vos 50 * n ^ 3 données sont appelées "temps d'exécution", mais c'est parce que le modèle utilisé pour les évaluations de vitesse suppose une machine avec plusieurs opérations de base, chacune d'entre elles prenant une unité de temps.

Dans votre cas, l’exécution de l’algorithme nécessite 50 * 500 ^ 3 unités de temps. Sur l'ordinateur A, chaque unité de temps est égale à 1 ms et sur l'ordinateur B, à 2 ms.

J'espère que cela donne un sens aux unités,
Asaf.