Comment calculer la grande-theta

Peut quelqu'un me fournir un temps réel exemple de la façon de calculer les gros thêta.

Est grand thêta quelque chose comme la moyenne des cas, (min-max)/2?

Je veux dire (un minimum de temps - big O)/2

S'il vous plaît corrigez-moi si je me trompe, merci

Avez-vous lu par exemple en.wikipedia.org/wiki/Big_O_notation, qui a un tableau de comparaison des différentes notations asymptotiques?
merci pour le lien, oui, j'ai vécu cela avant; le tableau décrit principalement abt big O et je suis difficile à suivre, cependant j'ai besoin de temps réel exemple pour obtenir plus de compréhension

InformationsquelleAutor Navin Leon | 2011-09-17

6

Grand-theta notation représente la règle suivante:

Pour les deux fonctions f(n), g(n), si f(n)/g(n) et g(n)/f(n) sont à la fois délimitée comme n pousse à l'infini, alors f = Θ(g) et g = Θ(f). Dans ce cas, g est à la fois une limite supérieure et une limite inférieure sur la croissance de f.

Voici un exemple d'algorithme:
```
def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min
```
Nous souhaitons évaluer la fonction de coût c(n) où n est la taille de la liste d'entrée. Cet algorithme va effectuer une comparaison pour chaque élément de la liste, de sorte c(n) = n.

c(n)/n = 1 qui reste bornée comme n va à l'infini, donc c(n) pousse pas plus vite que n. C'est ce que l'on entend par big-O notation c(n) = O(n). À l'inverse, n/C(n) = 1 reste aussi borné, de sorte c(n) pousse pas plus lent que n. Depuis, il pousse ni lent ni rapide, elle doit croître à la même vitesse. C'est ce que l'on entend par theta notation c(n) = Θ(n).

Noter que c(n)/n² est aussi borné, de sorte c(n) = O(n²) ainsi — big-O notation est simplement la limite supérieure de la complexité, de sorte que toute O(n) fonction est aussi O(n²), O(n³)...

Cependant, depuis n²/c(n) = n est pas bornée, alors c(n) ≠ Θ(n²). C'est la propriété intéressante de grand-theta notation: c'est à la fois une limite supérieure et une borne inférieure de la complexité.
- Comme je sais que c'est pas un gros thêta définition, il n'y a pas de quoi, dit-F(n)/G(n), il dit simplement: f(n) <= C1 g(n) et g(n) <= C2 f(n) ...., votre définition de contre-exemple, supposons que f = g = 0 pour tout n, de sorte que votre définition n'a pas de sens pour cet échantillon.
- Les deux définitions sont équivalentes, sauf pour f = g = 0.
- Pour l'exemple de l'algorithme ci-dessus: Faut-min-être d'abord l'infini négatif? Et seulement si min < valeur ?
InformationsquelleAutor Victor Nicollet
1

Grand theta est serré, lié, pour une fonction T(n): si: Omega(f(n))<=T(n)<=O(f(n)), puis Thêta(f(n)) est la difficulté liée pour T(n).

En d'autres termes Thêta(f(n)) "décrit" une fonction T(n), si les deux O [O] et l'Oméga, qui décrit le même T, avec la même f.

par exemple, un quicksort [avec un bon médian des choix], prend toujours au plus O(nlogn), à au moins Omega(nlogn), de sorte que quicksort [avec une bonne médian des choix] est Theta(nlogn)

EDIT:
ajout de l'analyse dans les commentaires:

À la recherche d'un tableau est toujours Theta(n). le Thêta fonction n'indique pas pire/meilleur des cas, mais le comportement du cas. j'.e, recherche pour un tableau T(n)=nombre d'ops pour le pire des cas. ici, évidemment T(n)<=O(n), mais aussi T(n)>=n/2, parce qu'au pire des cas, vous avez besoin pour effectuer une itération de l'ensemble de la baie, de sorte T(n)>=Omega(n) et donc Theta(n) est asymptotique lié.
- Quelle est la recherche d'un tableau de longueur n, ici le meilleur des cas est O(1) et au pire des cas est O(n), alors qu'est-ce que big thêta dans ce cas
- Léon: c'est encore Theta(n) le pire des cas, le comportement de la fonction Thêta n'est pas pire/meilleur des cas, c'est asymptotique en partance pour le cas où vous êtes la recherche pour. j'.e, recherche pour un tableau T(n)=nombre d'ops pour le pire des cas. ici, évidemment T(n)<=O(n), mais aussi T(n)>=n/2, parce qu'au pire des cas, vous avez besoin pour effectuer une itération de l'ensemble de la baie, de sorte T(n)>=Omega(n) et donc Theta(n) est asymptotique lié.
InformationsquelleAutor amit
0

De http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations, nous apprenons que "Big O" désigne une limite supérieure, alors que le "Big Thêta" désigne une limite supérieure et de limite inférieure, c'est à dire dans la limite de n va à l'infini:
```
f(n) = O(g(n))      -->    |f(n)| < k.g(n)

f(n) = Theta(g(n))  -->    k1.g(n) < f(n) < k2.g(n)
```
De sorte que vous ne peut pas en déduire Grand Thêta de Big O.
- Quelle est la recherche d'un tableau de longueur n, ici le meilleur des cas est O(1) et au pire des cas est O(n), alors qu'est-ce que big thêta dans ce cas
- Big-O, etc., ne sont pas sur le meilleur ou le pire des cas.
InformationsquelleAutor Oliver Charlesworth

Vous devez vous connecter pour publier un commentaire.