Jak określić najlepszy przypadek i najgorszy przypadek programu (algorytmu)?

Question

Załóżmy, że mam ten program, chcę porównać 2 listy wejściowe. Załóż tablicę A i tablicę B. Jak określić najlepszy i najgorszy przypadek funkcji?

Oto mój kod w [php]:

foreach($array_1 as $k){ 
    if(!in_array($k, $array_2)){ 
     array_push($array_2, $k); 
    } 
} 

Jaki jest najlepszy i najgorszy przypadek przypadku pętli for? Proszę podać kilka wyjaśnieniu, dziękuję :)

edycja:

Ponieważ moim celem jest, aby porównać 2 list, które mają na listach 1 wspólny element. Myślę, że mój powyższy kod jest błędny. Oto aktualizowane mojego kodu

foreach($array_1 as $k){ 
    if(in_array($k, $array_2)){ 
     array_push($array_3, $k); 
    } 
} 

I chyba byłoby:

Najlepszy przypadek: O (n)

Najgorszy przypadek: O (N * M)

Answer 1

LET'S wykonaj szybką analizę, następnie:

foreach($array_1 as $k) 

oznacza, że ​​operacja w obrębie będzie powtarzana dla każdego elementu tablicy. Oznaczmy rozmiar tablicy przez N.

Operacja ciągu:

if (!in_array($k, $array_2)) { 
    array_push($array_2, $k); 
} 

Istnieją 2 operacje tutaj:

• in_array
• array_push

array_push może być stała, a więc O(1), natomiast in_array jest bardziej prawdopodobne wyszukiwanie liniowe w array_2, które wykona jedną operację (znajdującą się jako pierwszy element) aż do długości operacji array_2.

Zauważ, że in_array stanowią jedyną zmienną tutaj:

• najlepszym wypadku: in_array powraca na pierwszym porównania -> wszystkie elementy array_1 są takie same, i albo array_2 była pusta lub są równe jego pierwszy element. Złożoność jest O(N) ponieważ mamy N elementy array_1
• najgorszym przypadku: za każdym razem badamy każdy element array_2 -> wszystkie elementy array_1 są różne i są one różne od poprzednich elementów array_2.Jeśli M jest długość array_2 gdy jest ona przypisana, to złożoność jest wzdłuż linii O(N * (N+M)), (N+M)/2 stanowiącego średni czas na poszukiwania w array_2 gdyż rośnie od M do M+N elementów i stałej 2 pozostawaniem w O notacji

Mam nadzieję, że to pomoże.

Answer 2

Generalnie z takim problemem po prostu patrzę na algorytm jako Dr Evil i pytam: "Jak mogę to zrobić, aby uzyskać najwięcej czasu?"

Answer 3

W notacji Big O chodzi o przybliżenia. Ułatwia porównywanie algorytmów.

Jeśli wyobrazisz sobie tablicę elementów, może to być szukanie N (musisz spojrzeć na każdy element, aby znaleźć żądany przedmiot), może to być log (N), jeśli masz zamówioną kolekcję lub nawet zamów 1, w zależności od rodzaju kolekcji.

Ważne jest, aby spojrzeć na swój algorytm i ustalić, jakie kluczowe operacje są powtarzane.

Foreach jest wyraźnie porządkiem N operacji, z definicji musisz operować na każdym elemencie na liście. O (N)

Następna jest twoja, jeśli InArray 2. To brzmi jak przeszukiwanie tablicy, która najprawdopodobniej byłaby nieuporządkowana, więc byłaby to kolejność N (wyszukiwanie liniowe). Więc twoja złożoność będzie teraz O (N * M). (dla każdego n elementów w tablicy 1, wykonaj wyszukiwanie porządku złożoności N względem tablicy 2).

Wreszcie masz tablicę push. Nie znam twojego środowiska, ale może to być kolejność 1 lub zamówienie N, jeśli tablica musi zostać ponownie przydzielona i skopiowana, aby rosnąć. Przyjmijmy, że zamówienie 1 jest proste. Zatem twoja złożoność w Big O to O (N * M).

Teraz najlepiej jest dla każdego elementu znaleźć jego odpowiednik przy pierwszej próbie i wykonać naciśnięcie tablicy, które byłoby O (N * 1 * 1) = O (N).

Najgorszym przypadkiem jest to, że każdego elementu nie można znaleźć na drugiej liście wymuszając pełne przeszukanie wszystkich elementów w tablicy 2. Zatem złożoność to O (N * M).

Twoi nauczyciele chcą zrozumieć twoje myślenie, więc pokaż im swoje założenia. Gorąco polecam przeczytanie dokładnego pytania i informacji, które otrzymałeś, zanim powinieneś oprzeć się na założeniach tutaj podanych, możesz być poinformowany o języku/platformie, która wskaże ci dokładną karę i algorytmy używane w każdym przypadku. Nadzieję, że pomaga :)