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


Câu hỏi 1:

1000n2+0.001n3Θ(n3)

Câu hỏi 2:

nlog(n)O(n)

Câu hỏi 3:

n2Ω(n)

Câu hỏi 4:

1012O(1)

Câu hỏi 5:

0.00001Θ(1)

Câu hỏi 6:

400n310nΘ(n3)

Câu hỏi 7:

n3+lognΩ(n)

Câu hỏi 8:

2n+1Θ(2n)

Câu hỏi 9:

2n+3+lognO(2n)

Câu hỏi 10:

22nO(2n)

Câu hỏi 11:

3nO(2n)

Câu hỏi 12:

log2nΘ(log10n)

Câu hỏi 13:

nΘ(logn)

Câu hỏi 14:

3n2+nO(n2)

Câu hỏi 15:

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

Câu hỏi 16:

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

Câu hỏi 17:

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

Câu hỏi 18:

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

Câu hỏi 19:

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

Câu hỏi 20:

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