Calcul de Big Theta à partir du Runtime?

Question

J'ai un programme qui calcule l'exécution en millisecondes de 4 fichiers .txt. Je dois alors calculer quel est le temps d'exécution du chargement en termes de thêta, et spécifier ce que n fait référence à l'entrée. Cependant, je ne comprends toujours pas exactement la grande notation thêta ou la notation asymptotique, d'ailleurs. Quelqu'un peut-il me donner quelques conseils? Ce sont les runtimes pour les fichiers:

Temps de fichier à charger

fichier1 18000ms

fichier2 48514ms

file3 121473ms

fichier4 622446ms

Answer 1

Il n'y a pas de façon générale à dériver une limite thêta sur l'exécution d'un programme à partir de son exécution empirique. Il peut y avoir des entrées que vous n'avez pas vu qui déclenchent les pires cas pathologiques (par exemple, l'algorithme simplex pour la programmation linéaire se dégrade en un temps exponentiel pire sur une classe étroite d'entrées) et vous n'avez aucun moyen de savoir si les tendances 'voir continuer à plus long terme. Si vous souhaitez obtenir la complexité de calcul empirique, une solution raisonnable consisterait à prendre vos données, à les tracer sur un axe log/log et à rechercher une ligne de meilleur ajustement. La raison pour laquelle cela fonctionne est qu'une ligne droite sur un tracé log/log correspond à un ajustement polynomial, donc il trouvera le meilleur polynôme approprié pour les données que vous avez. Tant que vous vous souvenez que votre réponse sera seulement aussi bonne que les données que vous fournissez, c'est une excellente façon d'exprimer la complexité.