0
J'ai juste une question simple, pourquoi est la grande notation O d'un tableau trié O (log N)? Ce sera un tableau trié.Trié tableau Big o notation
A
Répondre
4
notation Big O généralement fait sens dans le contexte d'un algorithme. Quelle opération envisagez-vous lorsque vous dites que la notation Big O est O (log n).
Si vous voulez rechercher, alors c'est O (log n) car vous pouvez utiliser la recherche binaire. Ce qui signifie essentiellement que vous regardez l'élément central de votre tableau, et s'il est plus grand que l'élément que vous recherchez, vous recherchez alors la moitié la plus grande (de la même manière), et vice versa (en supposant que vous n'avez pas encore trouvé votre élément bien sûr). Vous pouvez lire une description plus détaillée sur wikipedia.
À chaque étape de la recherche (en regardant l'élément du milieu), vous coupez la taille du tableau que vous devez rechercher en deux puisque vous pouvez maintenant savoir de quel côté de l'élément central doit se trouver votre élément de recherche. Bien sûr, cela ne fonctionne qu'avec des tableaux triés. Pour les tableaux non triés, le seul algorithme de recherche que vous pouvez utiliser est la recherche linéaire où vous examinez chaque élément du tableau qui prendra en moyenne n/2 inspections.
En général, Big O décrit les caractéristiques d'exécution des algorithmes, vous ne pouvez donc pas demander simplement quel est le Big O d'un tableau trié, il doit s'agir d'une opération sur le tableau. Cependant, vous pouvez considérer Big O en termes d'espace (mémoire) pris par une structure de données. Dans ce cas, un tableau trié prend encore l'espace O (n) pour stocker N éléments.
2
La question est un peu fausse. La complexité ne s'applique pas au tableau mais en fait à l'algorithme qui trie le tableau (je suppose que vous voulez dire la complexité d'exécution pas la mémoire). Donc en fonction de l'algorithme utilisé, le X dans O (X) pour trier un tableau peut varier fortement.
Vérifiez ces pages pour un démarreur sur la complexité en général et dans le cas particulier du tri en réseau.
Introduction to algorithm complexity
En quoi est-ce spécifique à Java? Ou pourquoi mentionner java dans le titre mais pas dans les tags? – jitter
De quelle opération parlez-vous d'un tableau trié? Lorsque vous parlez de "gros O", vous devez parler d'un algorithme, alors spécifiez-le. Est-ce l'insertion? Chercher? Trier? Quelle? –