Processing math: 100%

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 26/02/2025 14:00:00
Submission limit No limitation

Συνδεθείτε

[TP.02] Essayons de revenir les pieds sur terre


Question 1:

Si un algorithme a pris moins d'une micro-seconde à s'exécuter sur ma machine, puis-je affirmer que sa complexité temporelle est en O(1) ?

Question 2:

Si un algorithme a pris 6 mois à s'exécuter sur ma machine, est-ce que sa complexité temporelle est :

Question 3:

Si le nombre d'opérations primitives exécutées par un programme Python vaut 100n2, lorsque n est pair, et 20n2nlog2n, lorsque n est impair, puis-je affirmer que l'algorithme qu'il implémente a une complexité temporelle en Θ(n2) ?

Question 4:

Supposons que l'algorithme Magnifique et l'algorithme Splendide sont deux manières différentes de résoudre le même problème. Si je prouve que la complexité temporelle de l'algorithme Magnifique est, dans tous les cas, en Θ(n) alors que celle de l'algorithme Splendide est, dans tous les cas, en Θ(n2), est-il possible qu'un programme Python implémentant Splendide s'exécute plus vite qu'un programme Python implémentant Magnifique ?