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

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] Notations - Vrai ou faux ?

Dans les questions suivantes, n désigne un nombre entier positif. Il s’agit, par exemple, de la taille d’un problème à résoudre par un algorithme (par ex., trouver la valeur maximale dans un tableau de taille n). De plus, f(n) désigne une fonction mathématique qui dépend de n, par exemple le nombre d’opérations effectuées lorsque l’on exécute cet algorithme. Cette fonction est parfois décrite de façon explicite, par exemple : f(n)=1000n2+0.001n3.

Pour les questions ci-dessous, indiquez si les affirmations sont vraies ou fausses.


Pregunta 1:

1000n2+0.001n3Θ(n3)

Pregunta 2:

nlog(n)O(n)

Pregunta 3:

n2Ω(n)

Pregunta 4:

1012O(1)

Pregunta 5:

0.00001Θ(1)

Pregunta 6:

400n310nΘ(n3)

Pregunta 7:

n3+lognΩ(n)

Pregunta 8:

2n+1Θ(2n)

Pregunta 9:

2n+3+lognO(2n)

Pregunta 10:

22nO(2n)

Pregunta 11:

3nO(2n)

Pregunta 12:

log2nΘ(log10n)

Pregunta 13:

nΘ(logn)

Pregunta 14:

3n2+nO(n2)

Pregunta 15:

f(n)O(n)f(n)Ω(n)

Pregunta 16:

f(n)Ω(n)f(n)O(n)

Pregunta 17:

f(n)Ω(logn)f(n)Θ(logn)

Pregunta 18:

f(n)Θ(n3)f(n)Ω(n3)

Pregunta 19:

f(n)Ω(n2)f(n)Ω(n)

Pregunta 20:

f(n)Ω(n) et f(n)Θ(n)f(n)O(n)