J'essaie de comprendre la complexité de temps moyen d'un programme. J'ai réussi à trouver les temps d'achèvement pour certaines tailles d'entrée comme :

Taille-Temps

12 - 0,11552862

13 - 0,12365744

14 - 0,20763664

15 - 0,51893218

16 - 1.6423617

17 - 7.625521

Et j'ai créé un graphique. Graphique

Est-il possible de trouver la complexité temporelle avec seulement cette information. Je suis un peu perdu maintenant.

0
Georgi Spasov 8 févr. 2020 à 23:01

1 réponse

Meilleure réponse

Non, il n'est pas possible de trouver la complexité temporelle avec uniquement cette information. Sans regarder le code, déterminer la complexité temporelle n'est pas possible dans ce cas.

L'un (des nombreux) exemples simples où cette analyse de temps et d'entrée ne tiendrait pas, c'est si vous avez certaines instructions if dans votre code qui provoquent l'exécution de quelque chose que les entrées que vous avez fournies ne prennent pas en considération.

Vous pouvez vous référer à cette réponse :

Comment trouver la complexité temporelle d'un algorithme

Une autre réponse utile est :

Big O, comment le calculez-vous / l'approximez-vous?

0
Rahul P 8 févr. 2020 à 20:30