temps complexité de cette boucle while

2010-11-24 29 views 0 likes

Salut J'ai écrit un tel code et je veux savoir que: sa complexité temporelle est O (n)?temps complexité de cette boucle while

 DNode header = new DNode(null, null, null); 
     DNode trailer = new DNode(null, header, null); 
     header.next = trailer; 
     for (Point point : pointList) { 
      DNode node = new DNode(point, header, trailer); 
      dList.addLast(node); 
      header = node; 
     }

Je veux copier tous les objets du pointList(ArrayList) à un dList(Doubly-Linked list). merci

Source

2010-11-24 user472221

Répondre

Oui. Il n'y a qu'une seule boucle évidente ici, qui est O (n) - et tout dans la boucle est O (1), en supposant une implémentation raisonnable de la liste doublement liée.

Source

2010-11-24 06:37:52

J'ai un problème en ajoutant une liste à la fin de la liste doublement liée d'une manière telle que O (n) ou O (1)? – user472221

@ user472221: Eh bien, vous ne nous avez pas dit quelle implémentation vous utilisez, mais en général une liste doublement chaînée a O (1) temps pour l'insertion à chaque extrémité. Si vous utilisez 'LinkedList ' depuis le JDK, c'est certainement vrai. –

public void addLast (DNode v) { addBefore (bande-annonce, v); } – user472221

temps complexité de cette boucle while

Répondre

Questions connexes