Que représente exactement la grosse notation ?

Question

Je suis vraiment confus quant aux différences entre les notations big O, big Omega et big Theta.

Je comprends que le grand O est la limite supérieure et le grand Omega la limite inférieure, mais que représente exactement le grand (thêta) ?

J'ai lu que cela signifie lien étroit mais qu'est-ce que ça veut dire ?

Answer 1

Tout d'abord, la théorie

1. Big O = Limite supérieure O(n)

2. Thêta = Fonction d'ordre - thêta(n)

3. Omega = Q-Notation(limite inférieure) Q(n)

Pourquoi les gens sont si confus ?

Dans de nombreux blogs et livres, la façon dont cette déclaration est soulignée est la suivante

"C'est Big O(n^3)", etc.

et les gens confondent souvent comme le temps

O(n) == thêta(n) == Q(n)

Mais ce qui vaut la peine de garder à l'esprit est Ce ne sont que des fonctions mathématiques portant les noms O, Theta et Omega.

donc ils ont la même formule générale de polynôme,

Laissez,

f(n) = 2n4 + 100n2 + 10n + 50 alors,

g(n) = n4, Donc g(n) est une fonction qui prend une fonction en entrée et renvoie une variable de plus grande puissance,

Même f(n) et g(n) pour les explications ci-dessous.

Big O - Fonction (Fournit la limite supérieure)

Grand O(n4) = 3n4, car 3n4 > 2n4

3n4 est la valeur de Big O(n4) Tout comme f(x) = 3x

n4 joue un rôle de x ici donc,

En remplaçant n4 par x'donc, Big O(x') = 2x', Maintenant nous sommes tous les deux heureux Concept général est

Donc 0 f(n) O(x')

O(x') = cg(n) = 3n4

Mettre de la valeur,

0 2n4 + 100n2 + 10n + 50 3n4

3n4 est notre limite supérieure

Thêta(n) fournit une limite inférieure

Thêta(n4) = cg(n) = 2n4 Parce que 2n4 Notre exemple f(n)

2n4 est la valeur de Thêta(n4)

donc, 0 cg(n) f(n)

0 2n4 2n4 + 100n2 + 10n + 50

2n4 est notre limite inférieure

Omega n - Fonction d'ordre

Ce calcul permet de déterminer si la limite inférieure du temps est similaire à la limite supérieure,

Cas 1). La limite supérieure est similaire à la limite inférieure

if Upper Bound is Similar to Lower Bound, The Average Case is Similar

Example, 2n4  f(x)  2n4,
Then Omega(n) = 2n4

Cas 2). si la limite supérieure n'est pas similaire à la limite inférieure

in this case, Omega(n) is Not fixed but Omega(n) is the set of functions with the same order of growth as g(n).

Example 2n4  f(x)  3n4, This is Our Default Case,
Then, Omega(n) = c'n4, is a set of functions with 2  c'  3

J'espère que cela vous a expliqué !

Answer 2

Je veux juste vous donner une première impression et quelques idées de base. Ensuite, vous devriez faire plus de recherches sur Internet ou regarder des vidéos sur Youtube.

Pour le big-O-notation, il suffit de se rappeler qu'il existe deux fonctions : f(x) et g(x) et f(x) est inférieure à g(x) lorsque x est super grand. f(x) ∈ O(g(x))

Pour la big-omega-notation, il suffit de se rappeler qu'il y a deux fonctions : f(x) et k(x) et quand x est un super grand nombre, f(x) est toujours plus grand que k(x) f(x) ∈ Ω (k(x))

quand vous avez la première impression sur la big-o-notation et la big-omega-notation alors vous devriez faire une recherche sur Youtube.