Loading [MathJax]/jax/output/HTML-CSS/jax.js

Thông tin

Tác giả Vincent Branders, Pierre Dupont
Hạn chót 26/02/2025 14:00:00
Giới hạn nộp bài Không có giới hạn

Đăng nhập

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


Câu hỏi 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) ?

Câu hỏi 2:

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

Câu hỏi 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) ?

Câu hỏi 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 ?