• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

jamirooo

Double Linked List , contagem de nós visitados [Resolvido]

3 mensagens neste tópico

Boas! estou a estudar para o exame de algoritmos e estruturas de dados e o meu problema é o seguinte:

Tenho o seguinte excerto de código que representa uma Lista de nós ligados entre si

public class LinkedList <E> {
  private static class Node<E> {
      private E element ;
      private Node<E> next ;
      private Node<E> previous ;
      private Node ( E element , Node<E> previous , Node<E> next ) {
          this . element = element ;
          this . next = next ;
          this . previous = previous ;
     }
  }
  private Node<E> head ;
  private Node<E> tail ;
  int size ;
  ...
}

E de seguida é-me pedido que implemente "um método que devolva o i- ésimo elemento na lista. Note que o primeiro elemento na lista tem índice 1" .

Pois bem, eu fi-lo desta maneira:

/ /@ requires 1 <= index && index <= size ( ) ;
public E get (  int index ){
    if(index<= (size/2)){
        Node <E> aux = head;
        for(int i = 1 ;  i< index;  i++){
             aux = aux.next;
        }
     return aux.element;
}
    else{
        Node <E> aux = tail;
        for(int i = size; i> index ; i--){
             aux = aux.previous;
        }
    return aux.element;     
    }
}

                                               

Bem, eu penso que este método funcione (para ser sincero, ainda não o testei), mas o objectivo creio que ficou claro. O objectivo era que caso o index dado fosse para lá da metade do tamanho total da lista, em vez de percorrer todos os nós até essa posição, começaria a percorrer a lista do fim, de modo a percorrer menos nós.

As principais dúvidas são mesmo estas:

a) Quantos nós visita o método "quantos" abaixo? Apresente uma fórmula em função do número "n" de elementos na lista. Justifique.

/ /@ requires element ! = null ;
public int quantos ( E element ) {
   int result = 0;
   for ( int i = 1 ; i <= size ; i++)
       if ( element . equals ( get ( i ) ) )
          result ++;
   return result ;
}

b)Qual a complexidade temporal do método quantos? Justifique.

               

Pois, não estou bem a conseguir encontrar uma fórmula que defina o número de nós visitados, e quanto á complexidade temporal penso que seja O(n) mas também não tenho a certeza, se alguém me conseguisse dar uma mãozinha ficaria muito agradecido, cumprimentos! E obrigado desde já!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas.

Quanto ao método que devolve o "i-esimo da lista", acho que está certo, pelo menos eu também faria assim.

Quanto ao algoritmo do quantos, não te esqueças que também tens de contar com a eficiência do algoritmo get, visto que o usas. No pior dos casos, o método get percorrerá metade da lista, logo n/2. E como faz isso n vezes, ficará:

n * (n/2) <=> (n^2)/2

Logo, a complexidade será, penso que seja por arredondamento, O(n^2).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, acho que tens toda a razão. muito obrigado pela ajuda.  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora