Complexité (calcul du grand O)

J'ai travaillé sur certains problèmes de mon manuel qui concernent le calcul de la grande complexité O des algorithmes. Une des questions sur laquelle je suis perplexe n'a pas de réponse dans le dos et j'apprécierais toute contribution.Complexité (calcul du grand O)

Vous avez un tableau de longueur n-1 contenant des listes chaînées contenant des listes de mots. Chaque liste liée est d'abord triée, puis en utilisant le premier mot de la liste chaînée, le tableau est rapide. Quelle est la grande complexité O de cet algorithme?

Je sais déjà que:

Traversant une liste chaînée est O (n) type d'insertion est O (n^2) rapide Trier est (nlogn)

Je ne suis pas sûr de savoir comment d'aller sur le calcul de la complexité de l'ensemble algorithme

Source

2012-02-17 user1217222

Il faut donc n^2 pour insérer dans la liste puis nlg (n) pour trier et vous allez faire ça n-1 fois (non?) Donc: je dirais que c'est (n-1) * (n^2 + n * lg (n)) = ~ n^3 + n^2 * lg (n), si grand O (n^3)? – macduff

Votre question implique que le tableau est de taille n-1 et que toutes les listes liées sont de taille n. Est-ce exact? – hatchet

« chaque liste chaînée est triée première insertion »

Cela fait une complexité O(n) * O(m^2) ou O(n*m^2) - nous devons utiliser une lettre différente car la longueur de chaque liste n'est pas liée au nombre de listes.

"alors le tableau est quicksorted"

Cela ajoute O(n log n).

Total: O(n*m^2 + n log n), qui simpifies à O(n*m^2) (le n log n est non significatif par rapport à la n*m^2).

Source

2012-02-17 22:01:19

Je ne suis pas un expert en notation Big-O, donc ne soyez pas trop dur avec mon si je me trompe: p –

Techniquement parlant, vous devriez avoir O (max (nm^2, nlogn)). De plus, Quicksort est O (n^2) dans le pire des cas, donc à moins qu'il s'agisse d'une analyse de cas moyen, il serait techniquement plus correct de répondre O (max^2, n^2)). Je dis juste. Vous voulez un algorithme O (nlogn) du pire cas, essayez de fusionner ou de trier le tas. – Patrick87

Complexité (calcul du grand O)

Répondre

Questions connexes