Complexité du temps d'insertion dans la liste liée

Question

Toutes mes excuses Si cette question ressemble à une vérification de la solution, mais cette question a été posée dans mon test d'admission de diplômés et il y a beaucoup de choses à cheval sur ceci:

Quelle est la complexité du pire des cas d'insertion de $ N $ dans une liste liée vide, si la liste liée doit être maintenue dans la commande triée?

À mon avis, la réponse doit être $ o (n ^ 2) $ car dans chaque insertion, nous devrons insérer l'élément au bon endroit et Il est possible que chaque élément doive être inséré à la dernière place, me donnant une complexité de temps de 1 + 2 + ... (N-1) + n= o (n ^ 2) $

Cependant, la solution que j'ai dit que nous pouvons d'abord trier les éléments dans $ o (n \ journal n) $ et ensuite, nous pouvons les insérer un par un en $ O (n) $ , nous donnant une complexité globale de $ O (n \ log n) $ < / span>.

du libellé donné de la question, quelle solution est plus apte? À mon avis, depuis que la question des mentions "doit être maintenue dans une ordonnance triée", je suis enclin à dire que nous ne pouvons pas trier les éléments à l'avance, puis les insérer dans l'ordre trié.

Answer 1

La question indique uniquement que la liste cible doit être maintenue dans l'ordre trié. Cela ne dit rien à propos de toute autre structure de données que vous pouvez choisir d'utiliser. La solution proposée fait d'abord un certain prétraitement des arguments à insérer, puis l'insertion proprement dit. Cela est autorisé par la déclaration de problème.

Une raison pratique de faire cela, plutôt que d'insérer les éléments, alors trier, si l'objet de liste liée est partagé avec un autre fil qui l'oblige toujours à être triée. (Dans un tel scénario, vous devez vous assurer que l'insertion d'un élément est atomique.) Donc, cette question ne fait que faire des exigences étranges pour être étrange. C'est le genre d'exigences qui arrivent souvent dans le monde réel de la programmation.

Une autre solution avec la même complexité consisterait à insérer les éléments dans la liste cible, et à maintenir une structure de données parallèle des valeurs d'élément de mappage de la structure de données sur les pointeurs de noeuds dans la liste cible. Pour insérer chaque élément, trouvez l'élément précédent dans le mappage et insérez le nouvel élément après ce nœud. Cela suppose que le processus d'insertion crée les nœuds de la liste comme cela se passe (par opposition à la remplissage des nœuds vierges existants).

Cette question concerne davantage la compréhension de la lecture que des algorithmes. La façon dont il est libellé, c'est un peu une question d'astuce. C'est un peu mal formulé car il s'appuie sur une lecture précise, mais ne parvient pas à énoncer certaines hypothèses clés, telles que l'obtention des éléments pour insérer des coûts $ o (n) $ , la comparaison de deux éléments peut être effectuée dans $ o (1) $ et le domaine d'entrée est effectivement illimité (exercice: proposer un $ o (n) $ algorithme si les entrées sont des entiers dans la plage $ [1,42] $ ). Mais la réponse donnée est correcte.

Vous avez fait supposer qu'il n'y a aucun moyen d'utiliser une structure de données auxiliaire. Rien dans la déclaration de problème n'interdit en utilisant des structures de données auxiliaires. Un moyen simple d'interdire les structures de données auxiliaires serait d'exiger $ O (1) $ frais de mémoire.

Notez que même sous cette hypothèse, votre raisonnement est faux, ou du moins imprécis. Si vous savez que les éléments sont indiqués dans le bon ordre, vous pouvez maintenir un pointeur sur la queue de la liste et continuer à y insérer, ce qui prendrait $ O (n) $ . Le pire des cas n'est pas si chaque élément doit être inséré à la dernière position de la liste cible, mais à la dernière position atteinte lors de la déplacement de la liste d'une manière ou d'une autre. Le pire cas est en effet $ \ theta (n ^ 2) $ , mais pour prouver cela, vous devez prouver que la recherche du point d'insertion dans la liste prend $ \ theta (n) $ temps, et cela nécessite de prouver que la distance entre tout pointeur que vous avez dans la liste est limitée ci-dessous par $ \ oméga (n) $ . C'est le cas si vous avez un nombre constant $ a $ de pointeurs (vous supposez implicitement $ a= 1 $ , avec un seul pointeur au début de la liste), de sorte que vous devez traverser au moins $ k / a $ nœuds après $ K $ insertions dans le pire des cas.

Answer 2

La meilleure structure possible que je connaisse, sont des tas de fibonacci, vous pouvez insérer des éléments dans $ o (1) $ et extraire le minimum dans $ o (\ journal (n)) $ , cela signifie que si vous avez besoin d'un ordre trié de tous les éléments, il vous prend $ o (n \ log(N)) $ Tout en insérant des nouveaux éléments uniquement les coûts $ O (1) $ , je ne connais aucune autre structure qui pourrait suivre cela.

Answer 3

C'est vraiment une question délicate.Tout d'abord, la complexité de O (nlogn) s'applique uniquement aux algorithmes qui utilisent la comparaison entre leurs éléments (algorithme comparatif).Il existe également des algorithmes non comparatifs tels que RADIX TRY que leur complexité dépend de la taille des bits que les chiffres doivent être stockés en mémoire.Donc, si nous supposons que nous pouvons trier les chiffres à l'avance avec n'importe quel algorithme, nous pouvons également supposer que les chiffres sont naturels et que l'élément maximum est M <10, donc avec le tri radix, vous seriez le pire cas O (10n)= O (n).Si nous ne pouvons faire aucune hypothèse, vous avez raison.Si vous n'êtes autorisé à utiliser que des listes liées et rien de plus (aucun indexation de quelque nature que ce soit), la complexité est O (N ^ 2) (tri Bubble).

Answer 4

Il devrait être O (n). Suivez l'algorithme comme -

1) Si la liste liée est vide puis faites le nœud comme la tête et le retourner.

2) Si la valeur du nœud à insérer est plus petite que la valeur du nœud de tête, puis insérez le nœud au début et faites la tête.

3) dans une boucle, trouvez le nœud approprié après dont le nœud d'entrée doit être inséré.

Pour trouver le nœud approprié commence de la tête, Continuez à bouger jusqu'à ce que vous atteigniez un nœud que la valeur est supérieure à le nœud d'entrée.Le noeud juste avant que ce soit le nœud approprié

4) Insérez le nœud après le nœud approprié trouvé à l'étape 3