[fefler]

Mirce, dlaczego niektórzy podają złożoność metod dla kolekcji np O(n/4) albo O(n/2) a niektórzy O(n)? Zwyczajowo podając złożoność pomija się liczby poza n? (typu n/4 n/2 itd?) Tutaj przykładowo złożoności czasowe podane przez kolesia na Stackoverflow i złożoności podane na zdjęciu.

For LinkedList

get(int index) is O(n/4) average
add(E element) is O(1)
add(int index, E element) is O(n/4) average
but O(1) when index = 0 <--- main benefit of LinkedList
remove(int index) is O(n/4) average
Iterator.remove() is O(1) <--- main benefit of LinkedList
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList
Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)

For ArrayList

get(int index) is O(1) <--- main benefit of ArrayList
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n/2) average
remove(int index) is O(n/2) average
Iterator.remove() is O(n/2) average
ListIterator.add(E element) is O(n/2) average
Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)

#java #naukaprogramowania

[MegaKox]

@fefler: to nie ma znaczenia. Wszystko to ma złożoność liniową

[fefler]

@MegaKox: Nie ma znaczenia, że np remove ma u ArrayList O(n/2) a w LinkedList O(n/4)? Zawsze to 2 razy szybciej.

[frotewaus]

@fefler: jeżeli n-elementową listę przeszukujesz po kolei, to statystycznie w połowie znajdziesz to czego szukasz. Można to wtedy zapisać jako O (n /2).
W najgorszym przypadku znajdziesz to na samym końcu - czyli O (n)

Takie porównanie ma jednak sens tylko w kontekście tej samej metody. Gdy porównujesz różne metody, praktycznie nigdy nie jesteś w stanie tak precyzyjnie określić zależności między nimi - ustalasz więc jedynie dla obu zależność od n.

[A.....t]

@fefler: chodzi o to, jak zmienia się ten czas w zależności od liczby elementów

[UberRam]

@fefler: liczy sie rzad zlozonosci, wszelkie stale sa nieistotne w jej szacowaniu. Rzad O jest pesymistycznym szacunkiem ("zlozonosc nie wieksza niz ..") dlatego zawsze daje sie szacunek dla worst-case.

[A.....t]

@fefler: jeśli ktoś chce porównywać szybkość to samo n/2 czy n/4 nie wystarczy, bo te operacje mogą działać dłużej lub krócej

[GotoFinal]

@UberRam: @fefler: no czasem się jednak uwzględnia ten nie najgorszy przypadek, bo są algorytmy gdzie najgorszy przypadek ma bardzo małą szansę zaistnieć, ale wtedy też często podają oba, np O(1) i O(N) w najgorszym przypadku.
Tak jak właśnie z ArrayList.add