Processing math: 100%

Informações

Autores Vincent Branders, Pierre Dupont
Prazo de entrega 26/02/2025 14:00:00
Limite de submissão No limitation

Entrar

[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.


Questão 1:

1000n2+0.001n3Θ(n3)

Questão 2:

nlog(n)O(n)

Questão 3:

n2Ω(n)

Questão 4:

1012O(1)

Questão 5:

0.00001Θ(1)

Questão 6:

400n310nΘ(n3)

Questão 7:

n3+lognΩ(n)

Questão 8:

2n+1Θ(2n)

Questão 9:

2n+3+lognO(2n)

Questão 10:

22nO(2n)

Questão 11:

3nO(2n)

Questão 12:

log2nΘ(log10n)

Questão 13:

nΘ(logn)

Questão 14:

3n2+nO(n2)

Questão 15:

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

Questão 16:

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

Questão 17:

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

Questão 18:

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

Questão 19:

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

Questão 20:

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