Jaki jest najlepszy algorytm z tych 2 (w Javie) do usuwania określonych wartości z listy?
1: używanie listy tablic
2: za pomocą połączonej listy

for (int i = arraylist.size()-1; i >= 0; i--) {
        if(arraylist.get(i).getValue() < 20)
            list.remove(i);
    }

Lub

for (int i = linkedlist.size()-1; i >= 0; i--) {
        if(linkedlist.get(i).getValue() < 20)
            list.remove(i);
    }

Jaka jest złożoność tych 2 algorytmów? (jeśli w pętli for)? Myślę, że to O(n), ale nie jestem pewien...

-3
Johan 4 marzec 2012, 01:57

2 odpowiedzi

Najlepsza odpowiedź

LinkedList

Nie powinieneś nigdy, przenigdy iterować połączonej listy, indeksując ją. Indeksowanie do połączonej listy to operacja O(n). Oto podział:

  1. Iterujesz po rozmiarze listy: n kroki => O(n) operacja.
  2. Indeksujesz go, aby uzyskać przechowywaną wartość: operacja O(n).
  3. Indeksujesz do niego, aby usunąć przechowywaną wartość: operacja O(n).

W każdym kroku iteracji od 1. powyżej wykonujesz operację O(n) dwa razy. To jest 2n * O(n), co jest równoważne O(n^2).

Aby usunąć z połączonej listy w O(n) czasie, musisz użyć wewnętrznego mechanizmu iteracji do iteracji po niej oraz do iterator.remove() elementów z niej, jeśli spełniają Twoje kryteria.

ArarayList

W przypadku listy opartej na tablicy problem polega na tym, że operacja usuwania jest operacją O(n): elementy po prawej stronie usuniętego elementu muszą zostać przesunięte w lewo. Przejście od prawej strony niczego nie rozwiązuje, ponieważ zapisane wartości nadal muszą zostać przeniesione w lewo, jeśli usuniesz coś po lewej stronie tablicy. Awaria:

  1. Iterujesz po rozmiarze listy: n kroki => O(n) operacja.
  2. Indeksujesz go, aby uzyskać przechowywaną wartość: operacja O(1).
  3. Usuwasz przechowywaną wartość: operacja O(n).

Co daje O(n^2) wydajność.

Nie możesz usunąć elementów z ArrayList bez tego rodzaju wydajności, ponieważ operacja usuwania to O(n) (chyba że tablica jest posortowana i kopiowanie jej części jest uważane za O(n) operacja).

1
Irfy 4 marzec 2012, 02:20

Jeśli sortedList jest instancją LinkedList, drugi algorytm ma złożoność O(n^2) ze względu na złożoność linkedlist.get(i) O(n).

0
Roman 4 marzec 2012, 02:03