Processing math: 100%

Información

Autor(es) Vincent Branders, Pierre Dupont
Fecha de entrega 26/02/2025 14:00:00
Tiempo límite de envío Sin límite de envío

Inicia sesión

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


Pregunta 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) ?

Pregunta 2:

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

Pregunta 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) ?

Pregunta 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 ?