Złożoność czasu wyszukiwania

Wyszukiwanie binarne to paradygmat podziału. Szuka elementu w posortowanej tablicy. W tym artykule rozważane jest tylko sort. Element do wyszukiwania nazywany jest wartością docelową. Wartość docelowa może, ale nie musi być znaleziona w tablicy.

Wyszukiwanie zaczyna się od porównania wartości docelowej z środkowym elementem posortowanej tablicy. Jeśli liczba elementów w tablicy jest równa, przedmiot w połowie liczby jest uważany za element środkowy. Jeśli wartość docelowa jest taka sama jak pozycja środkowa, znaleziono wskaźnik wartości docelowej. Jeśli nie są takie same, wartość docelowa jest większa lub mniejsza niż przedmiot środkowy. Jeśli jest większy, wówczas dolna połowa tablicy zostanie porzucona, aby poszukiwania kontynuowane w górnej połowie. Jeśli jest mniejszy, wówczas górna połowa tablicy zostanie porzucona, aby poszukiwać w dolnej połowie.

Wyszukiwanie trwa, dzieląc połowę wybraną na dwa. Porównanie wartości docelowej a środkowym elementem tej nowej połowy jest dokonywane. Jeśli nie są takie same, ta połowa jest ponownie podzielona na dwa i z tych samych powodów poprzedniej połowy została podzielona. Jeśli wartość docelowa nie jest taka sama jak nowy element środkowy, podział kontynuuje.

Gdy wartość docelowa i wartość mediana (pozycja) są takie same, to podbija. Tam, a potem wyszukiwanie kończy się. Jeśli wartość docelowa nie ma w tablicy, wyszukiwanie zatrzyma.

Ten artykuł ma na celu uznanie złożoności czasu w celu szybkości wyszukiwania binarnego.

Treść artykułu

• Wprowadzenie - patrz wyżej
• Ilustracja wyszukiwania binarnego
• Złożoność czasu i wyszukiwanie binarne
• Kodowanie w c
• Wniosek

Ilustracja wyszukiwania binarnego

Rozważ posortowaną listę:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Gdzie należy przeszukać liczbę całkowitą 3. Oczywiście, wyszukiwanie od samego początku zajmie trzy operacje. Jednak korzystanie z wyszukiwania binarnego podejmie cztery główne operacje w następujący sposób:

Wartość docelowa to 3. Dzielenie listy na dwa sprawia, że ​​8 element środkowy.

Jest 8 taki sam jak 3?

NIE. Ponieważ 3 jest mniej niż 8, wyszukiwanie skupi się na dolnej połowie. To jest jedna główna operacja wykonana.

Dzielenie na dwa ponownie sprawia, że ​​4 nowy element środkowy.

To 4 takie same jak 3?

NIE. Ponieważ 3 jest mniej niż 4, wyszukiwanie skupi się na nowej dolnej połowie. To jest druga główna operacja wykonana.

Dzielenie na dwa ponownie sprawia, że ​​2 nowy element środkowy.

To 2 takie same jak 3?

NIE. Ponieważ 3 jest większe niż 2, wyszukiwanie skupi się na nowej górnej połowie. To jest trzecia główna operacja wykonana.

Dzielenie na dwa ponownie tworzy 3 nowy element środkowy, połowy (podpis) długości, jeden. Nowy i ostatni środkowy przedmiot ma teraz 3.

To 3 takie same jak 3?

Tak. Znaleziono wartość docelową. To jest czwarta i ostatnia główna operacja.

Gdy jest 16 pozycji, można wykonać maksymalnie 4 główne operacje. Gdyby było 16 pozycji, a wartość docelowa była w zakresie i nie można było znaleźć, 4 główne operacje nadal miałyby miejsce. Na przykład na poniższej liście:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

Nadal jest 16 pozycji. Wartość docelowa 3 zakończyłaby się w wartości 5, z nadal 4 głównymi operacjami.

Złożoność czasu i wyszukiwanie binarne

Najgorsza wydajność

Najgorsza wydajność odnosi się do przypadku, w którym wartość docelowa znajduje się na ostatniej głównej operacji lub wartość docelowa znajduje się w zakresie wartości i nie jest znaleziona na ostatniej głównej operacji.

Gdy liczba elementów wynosi 16, maksymalna liczba operacji zawsze wynosi 4.

16 = 2⁴
4 = log₂(16)

Niech n będzie 16. Więc,

4 = log₂(N)

Jeśli n wynosi 8, maksymalna liczba operacji wynosi 3 = log₂(8). Jeśli n wynosi 32, maksymalna liczba operacji wynosi 5 = log₂(32).

Mówi się, że najgorsze złożoność czasu (prędkość względna) do wyszukiwania binarnego brzmi:

O (log₂(N))

Gdzie duże O i jego nawiasy mają dziennik₂(n) jest notacją złożoności czasu. Jest po prostu napisany jako:

O (log n)

Najlepsza wydajność

Załóżmy, że wartość docelowa wynosiła 8 dla pierwszej listy powyżej. W takim przypadku pierwsza główna operacja znalazłaby pozycję wartości docelowej. To jest najlepsza wydajność. Złożoność czasu dla tego najlepszego występu jest napisana jako:

O (1)

Gdzie 1 oznacza jedną główną operację.

Kodowanie w c

Funkcja wyszukiwania binarnego kodu C to:

#włączać
int binarySearch (int arr [], int bel, int n)
int loindex = 0;
int upindex = n - 1;
// upewnij się, że nadal mamy elementy na liście do wyszukiwania
while (loindex cel)
UPINDEX = Middleindx;
w przeciwnym razie
Loindex = Middleindx + 1;


// Zwróć liczbę ujemną, gdy nie możemy znaleźć celu w tablicy
zwrot -1;

Loindex oznacza najniższy wskaźnik połowy (podpis). UpIndex oznacza najwyższy wskaźnik połowy (podpis). Na początku Loindex to 0, a Upindex 15, gdy n ma 16. Warunka pętli w pobycie zapewnia, że ​​podział trwa do momentu, gdy Loindex będzie taki sam jak Upindex, jeśli wartość docelowa nie została jeszcze znaleziona.

Odpowiednią główną funkcją C dla tego kodu jest:

int main (int argc, char ** argv)

int n = 16;
int Target = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
int indexfound = binarySearch (ARR, Target, N);
printf („%d \ n”, indexfound);
powrót 0;

Wniosek

W tym artykule omówiono złożoność binarnego czasu wyszukiwania i podkreślono, co następuje:

Najgorsze złożoność czasu dla wyszukiwania binarnego jest:
O (log n)

Najlepsza złożoność czasu do wyszukiwania binarnego jest:
O (1)