najbardziej skuteczny sposób, aby uzyskać największą liczbę ze zbioru liczb całkowitych

Question

pytanie: najbardziej skuteczny sposób, aby uzyskać największą liczbę ze zbioru liczb całkowitych

Byłem niedawno dyskusji na to pytanie, miałem 2 rozwiązania w umyśle. 1) Iteracja nad kolekcją i znalezienie najwyższego numeru (kod poniżej) 2) Użyj algorytmu sortowania.

Pierwsza metoda będzie musiała O (n) wydajności

int getHighestNumber(ArrayList<Integer> list) 
    {  
     if(list != null && list.size() > 0) 
     { 
      if(list.size() == 1) 
       return list.get(0); 

      int maxNum = list.get(0); 
      for(int item:list) 
      { 
       if(item > maxNum) 
        maxNum = item; 
      } 
      return maxNum;   
     } 
     return null; 
    } 

Moje pytanie brzmi: „Czy każdy algorytm sortowania go pobić (na skali czasu) na danym wejściu do np. Czy kolekcja jest już posortowana lub nie?" Czy jest jakiś inny sposób lepszy od tego?

Answer 1

Jeśli kolekcja jest już posortowane, można znaleźć największy element w O(1) (zakładając Collection obsługuje losowego dostępu lub O(1) dostęp do końca Collection posiadających największy element - jeśli największym elementem jest pierwszy, żadnej kolekcji będzie daje ci dostęp O(1) poprzez jego Iterator). W takim razie nie musisz tego sortować.

Każde sortowanie zajmie co najmniej O(n), gdy dane wejściowe zostaną posortowane (i co najmniej O(nlog(n)), gdy nie jest), ponieważ nie można sprawdzić, czy dane wejściowe są sortowane bez przechodzenia przez wszystkie elementy. Dlatego algorytmy sortowania nie mogą pokonać Twojego rozwiązania O(n).

Answer 2

Twoje pytanie wskazuje na jego własną odpowiedź. To zależy od źródła samej kolekcji. Oznacza to, że im więcej wiesz o zestawie danych, tym szybciej możesz opracować heurystykę, aby uzyskać odpowiedź, której potrzebujesz.

Dlatego, jeśli lista jest już posortowane, a następnie lista [0] lub lista [len-1] będzie najwyższym ...

Odpowiedź wtórnym jest również zależna od „Jak często będzie lista być przeszukany? ". Jeśli jest to jednorazowe wyszukiwanie, to najszybsza jest tylko iteracja listy dla najwyższej. Jeśli będziesz robić to wielokrotnie (np. Zbierając różne dane), to najpierw sortowanie za pomocą szybkiego sortowania może być najlepszym wynikiem.

Answer 3

Twoje pytanie jest takie, że istnieją dwie możliwości znalezienia maksymalnej wartości nieposortowanej listy.

Wariant 1: stosując metodę o której mowa w pytaniu getHighestNumber

Opcja 2: sortowania listy używając świat najbardziej skuteczny algorytm sortowania, a następnie podjąć ostatnią wartość listy.

Więc co jest najlepszym rozwiązaniem pod względem wydajności.

Moja odpowiedź: Opcja 1, jeśli tablica nie jest posortowana żaden algorytm sortowania można pokonać wariant 1.

Answer 4

Z Java 8 można znaleźć max pomocą Stream API, ale to nie rozwiązuje O (n) problem.Jednak dostęp do elementu jest mniej kosztowny obliczeniowo niż normalny iterator;

list.stream().mapToInt(i -> i).max().getAsInt(); 

Answer 5

Oto mój ulubiony argument, który zawsze wykorzystuje się szybkie sędzia takim pytaniem:

musiał użyć przynajmniej O(N) tylko patrzeć wszystkie elementy, które jest I/O czas.

Niewiele myśląc zbyt wiele, może przekonać się, że nie może pokonać wszelkie algorytmy O(N) algorytmów pod względem złożoności. Mam nadzieję, że to ma sens.