Czy Collections.sort(list) sprawdza, czy list jest już posortowany, czy może jest O (1) z innego powodu?
Czy to jest dobry pomysł, aby mieć flagę posortowaną i ustawić ją na true/false po wywołaniu sort()/dodanie elementu do listy?Java - Czy wywołanie sort() na już posortowanej liście jest operacją O (1)?
Jak ustalić, czy jakakolwiek lista jest sortowana bez patrzenia na nią? To nie będzie O(1). Ustalenie, czy lista jest posortowana, zajmuje co najmniej O(n).
Oznaczałoby to, że jeśli Collections.sort zadał sobie trud sprawdzenia, czy lista została posortowana jako pierwsza, każda operacja sortowania musiałaby zajmować średnio O(n) + O(n log n).
Nie ma mowy, że to O (1), nie można sprawdzić, czy kolekcja jest posortowana szybciej niż O (n). Posiadanie flagi powinno być w porządku, ale trudno powiedzieć na pewno, nie wiedząc, co dokładnie robisz.
Ogólnie sortowanie już posortowanej listy nie przyspiesza (oprócz prostych sortowań, takich jak sortowanie bąbelkowe). W niektórych przypadkach sortowanie wstępne jest wolniejsze.
W przypadku Collections.sort() nie jest szybsze sortowanie posortowanej listy.
W rzeczywistości nie do końca prawdziwe. iirc Java używa Timsort do pewnych rzeczy zaczynając od Javy7, a Timsort jest całkiem niezły w sortowaniu częściowo posortowanych list, tj. lepiej niż teoretyczne 'O (n log n)' – Voo
+1 dla wstępnie posortowanego wolniej w niektórych przypadkach –
W rzeczywistości z Java7, Java przeszła z mergesort na TimSort (nazwa pochodzi od pythona dev Tima Petersa, który zaimplementował go najpierw dla cpython) dla niektórych zadań sortowania.
Chociaż nie jest to O (1), sortowanie już posortowanej lub częściowo posortowanej listy za pomocą TimSorta jest znacznie bardziej wydajne niż sortowanie całkowicie losowego zestawu danych (w późniejszym czasie nie ma możliwości uzyskania większej skuteczności niż O(n log n) dla sortowania porównawczego , nie dotyczy to danych losowych).
OK, ale prawdopodobieństwo, że osoba pytająca używa Java 7 jest dość niskie (niektórzy twierdzą, że 18% http://blog.jelastic.com/2011/12/07/java-7-adoption-grows-to-18-percent/) –
@vitalik Prawdopodobieństwo, że przyszli czytelnicy będą używać Javy 7 lub późniejszej, może zwiększyć się tylko z tego miejsca. SO jest pomyślane jako archiwum informacji, a nie forum. – EJP
@EJP Biorąc pod uwagę, że vitalik nie przesłał mi mojego postu, kiedy opublikował ten komentarz, czy przypadkowo pomyliłeś się? W przeciwnym razie jestem zaskoczony, że ktoś może zgodzić się z moim postem. b2t: Myślę, że tak długo, jak wyraźnie zaznaczam, że dotyczy to tylko Java7 +, ilu ludzi używa jakiejkolwiek wersji, nie jest zbyt ważne - 18% to wciąż sporo osób. – Voo
mówiąc ściśle, O (1) nie oznacza 1 indeksu :) – unbeli
@unbeli +1 poprawił moją odpowiedź. – Aidanc
A 'O (n) + O (n log n)' jest takie samo jak 'O (n log n)' :) – unbeli