Existe-t-il un algorithme O (nlog (n)) pour inverser une liste simplement liée?

Question

Dans les commentaires à this answer une idée est soulevée que l'inversion d'une liste simplement liée pourrait seulement être faite en O (nlog (n)), pas O (n) temps.

Ceci est définitivement faux - une inversion O (n) n'est pas un problème - il suffit de parcourir la liste et de changer les pointeurs au fur et à mesure. Trois pointeurs temporaires sont requis - c'est de la mémoire supplémentaire constante. Je comprends complètement que O (nlog (n)) est pire (plus lent) que O (n). Par curiosité - ce qui pourrait être un algorithme O (nlog (n)) pour inverser une liste simplement liée? Un algorithme avec une mémoire supplémentaire constante est préférable.

Answer 1

Je pense que vous êtes confus. Vous dites O (n log (n)) qui est en fait pire que O (n). Voulez-vous dire O (log n)? Si oui, la réponse est non. Vous ne pouvez pas inverser une liste chaînée dans O (log n). O (n) est trivial (et la solution évidente). O (n log (n)) n'a pas beaucoup de sens.

Editer: Ok, donc vous voulez dire O (n log (n)). Alors la réponse est oui. Comment? Facile. Vous triez la liste:

1. Comptez la longueur de la liste. Coût: O (n);
2. Créer un tableau de même taille;
3. Copiez les éléments de la liste liée dans le tableau dans aléatoire en mettant l'ordre d'origine dans l'élément. Par exemple: [A, B, C] -> [(B, 2), (C, 3), (A, 1)]. Coût: O (n);
4. Trier le tableau à l'aide d'un tri efficace (par exemple tri rapide) dans l'ordre original inversé, par exemple [(C, 3), (B, 2), (A, 1)]. Coût: O (n log (n));
5. Créez une liste liée à partir du tableau inversé. Coût: O (n).

Coût total: O (n log (n))

En dépit de toutes les étapes intermédiaires, le genre est l'opération la plus coûteuse. Les autres étapes O (n) sont constantes (ce qui signifie que le nombre de pas n'est pas un facteur de n), donc le coût total est O (n log (n)).

Edit 2: Au départ, je ne l'ai pas mis les éléments de liste dans un ordre aléatoire, mais réalisé que vous pourriez arguer qu'une sorte efficace sur une liste déjà triée était inférieure à O (n log (n)), même si vous l'inversaient. Maintenant, je ne suis pas complètement convaincu que c'est le cas mais la révision ci-dessus supprime cette critique potentielle.

Et oui, c'est une question pathologique (et une réponse). Bien sûr, vous pouvez le faire en O (n).

Answer 2

Eh bien ...

Vous pouvez utiliser une récursivité qui accepte une liste, et il intervertit, en se faisant appeler avec deux moitiés de la liste chaînée, où si l'entrée est à seulement deux noeuds, il les intervertit.

Ceci est très inefficace mais je crois que c'est O (nlog (n)) ...

Quelque chose comme ce qui suit dans le code pseudo (en supposant que vous avez une fonction len qui retourne la longueur d'une liste dans O (n) et une fonction sub_list(list, start_id, end_id) qui retourne un sous-ensemble de la liste à partir de START_ID et se terminant à end_id en O (N)):

function invert(list) 

    if len(list) == 1 return list 

    if len(list) == 2: 
     new_list = list.next 
     new_list.next = list 
     return new_list 

    middle_of_list = len(list)/2 <-- integer division 

    first_half = invert (sub_list(list, 1, middle_of_list)) 
    second_half = invert (sub_list(list, middle_of_list+2, len(list)) 

    first_half.next = second_half 

    return first_half 

Answer 3

Chaque algorithme O (n) est également O (n log n), donc la réponse est oui.

Answer 4

idée stupide, mais O (n log n) et non O (n)

• assignez à chaque élément d'une liste d'un ID unique. L'ID de chaque successeur doit être supérieur à l'ID de l'élément (O (n))
• Trier les éléments par ordre croissant en utilisant la clé id comme clé en utilisant un algorithme de tri par comparaison (O (n log n))
• Créer une nouvelle liste en utilisant l'ordre donné par le tri des éléments (O (n))

Answer 5

Si vous êtes pédant alors cet algorithme est O (n log n), parce que les pointeurs sont de taille au moins log n et doivent être assignés n fois.

Mais en réalité, les machines ont une taille de mot fixe, ce qui n'est généralement pas pris en compte.

Answer 6

Si la question est réellement pour un algorithme de Ω (nlgn), peut-être cet algorithme trop compliqué fera-t-il?

• construire une structure arborescente équilibrée de la liste liée
• chaque feuille contient à la fois la valeur d'origine de la liste liée, et un numéro d'index de la valeur dans la liste liée; utiliser l'index comme la clé arbre
• traverse l'arbre pour signaler tous les leafs dans l'ordre inverse de l'indice d'origine
• créer une nouvelle liste chaînée de la mise en correspondance des valeurs