J’apprends un cours Coursera sur la complexité temporelle. Je rencontre cela dans une vidéo et je pense que quelque chose ne va pas. “Supposons donc que nous ayons un algorithme dont la durée d’exécution est à peu près proportionnelle à n et que nous souhaitons qu’il l’exécute sur une machine fonctionnant à environ un gigahertz. Quelle taille d’entrée pouvons-nous gérer de telle sorte que nous puissions terminer le calcul en une seconde ? ? ” (CPU 1 GHz (10 ^ 9 cycles par seconde))
“Eh bien, s’il fonctionne à environ une taille n, vous pouvez gérer environ un milliard d’entrées, avant que cela ne prenne plus d’une seconde” (10^9 / 10^9)
“Si cela fonctionne comme n au carré, c’est bien pire. Vous ne pouvez gérer que des entrées d’une taille d’environ 30 000 avant que cela ne commence à prendre plus d’une seconde.” n = 30 000, (30 000)^2/10^9 = 0,9 s ~ 1 s
“Si les entrées sont de taille 2 au n, c’est incroyablement mauvais, vous ne pouvez gérer que des entrées d’une taille d’environ 30 en une seconde” 2^30/10^9 ~ 1,07 sec
Avec une complexité n log(n), si la taille d’entrée n est de 10^9, alors cela devrait prendre 10^9 * log(10^9) / 10^9 = 9 secondes, n’est-ce pas ? D’une manière ou d’une autre, cela montre 30 secondes dans la vidéo. Il a également indiqué que si n = 10 ^ 7,5, la durée d’exécution est de 1 seconde, ce qui est également erroné dans mon calcul.
J’ai calculé chaque cas avec la complexité n, n^2, 2^n et tout allait bien, seul le cas nlog(n) était foiré
Voici la photo pour plus de détails : https://i.upanh.org/2022/04/11/nlogn.jpg[^]
Lien vers la vidéo du cours (3h40 à 17h00 est la partie) : https://www.coursera.org/lecture/algorithmic-toolbox/asymptotic-notation-zI8dH[^]
J’ai modifié la question pour qu’elle ressemble à la vidéo du cours que j’ai regardée
Ce que j’ai essayé :
I calculated every case with the n, n^2, 2^n complexity and everything was right, only nlog(n) case messed up
Solution 1
Citation:Si la taille d’entrée n est de 10^9, alors cela devrait prendre 10^9 * log(10^9) / 10^9 = 9 secondes, n’est-ce pas ?
Non ! Vous ne calculez pas le temps d’exécution à partir de la notation Big O, du moins pas par lui-même.
La notation Big O vous indique la complexité des catégories d’un algorithme, pas le runtime, pas directement.
Lorsque vous disposez d’un runtime pour une taille de données donnée, la complexité Big O vous permet d’évaluer le runtime pour une autre taille de données.
votre timing de 1 seconde pour les données de 20 à 10 ^ 6 signifie que vous devez passer au timing en millisecondes pour obtenir un timing significatif.
Solution 2
Le grand O ne donne pas l’heure exacte de l’exécution. Voir par exemple Notation du grand O — Wikipédia[^] (Propriétés sections, multiplication par une constante).
Solution 3
Pour ajouter à ce que disent les autres, vous ne pouvez de toute façon pas assimiler les cycles d’horloge directement au temps d’exécution – certaines opérations de la machine prennent n cycles pour s’exécuter, d’autres peuvent être n * 2. Pour ajouter à cela, les processeurs modernes sont en pipeline – donc certaines instructions peut démarrer pendant que d’autres sont en cours d’exécution, mis en cache – le temps d’exécution peut donc dépendre de la durée de la dernière exécution d’une instruction et de la disponibilité de ses données dans les caches L1, L2 ou L3, de la disponibilité de cœurs libres à exécuter, ainsi que d’une foule d’autres détails.
Vous ne pouvez pas simplement dire “ma vitesse d’horloge est X, donc mon temps d’exécution est X * Y” – il y a beaucoup trop d’autres facteurs qui l’influenceront.
Solution 5
30 secondes, c’est à peu près correct si c’est un journal2(n). enregistrer2(1000) ~= 10.
MODIFIER: Les algorithmes O(n log(n)) divisent souvent de manière récursive le problème en deux, résolvent chaque partie séparément, puis combinent les solutions. C’est pourquoi se connecter2 est généralement implicite. Mergesort est un bon exemple.
Solution 6
la notation grand O vous indique uniquement comment le temps d’exécution sera changement lorsque la « taille » du problème change, cela ne fournit pas d’estimation réelle pour un cas spécifique.
En d’autres termes, il existe une inconnue, par exemple O(n2) pourrait signifier
time_needed = constant * n * n
où personne ne dit quelle est la valeur de la constante, donc aucune valeur concrète pour time_needed.
L’exemple vous indique seulement qu’un problème deux fois plus important prendra quatre fois plus de temps à être résolu.
コメント