Wpisany przez Tomasz Lubiński
piątek, 04 września 2009 19:47
Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej zadany element x. Niech będzie to tablica a o indeksach od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1], a[2], a[3], ..., a[n-1], a[n].
Jeżeli przyjrzymy się dokładnie klasycznemu algorytmowi przeglądania tablicy w poszukiwaniu elementu:
zauważymy, że dla każdego elementu wykonywane są dwa porównania:
Liczbę porównań można zredukować wykorzystując algorytm wyszukiwania z wartownikiem. Nazwa tego algorytmu bierze się ze sposobu, w jaki wykorzystywany jest element szukany x.
By odnaleźć element x podejmiemy następujące kroki:
W stosunku do klasycznego algorytmu wyszukiwania oszczędzamy czas na sprawdzaniu czy osiągnęliśmy koniec tablicy. Sprawdzenie to występuje raz - po odnalezieniu elementu szukanego, a nie tak jak poprzednio przed każdym sprawdzeniem kolejnego elementu.
Operację odnajdowania elementu w tablicy z wartownikiem możemy zapisać następującym schematem blokowym:
Algorytm ten mimo, że jest szybszy od zwykłego wyszukiwania to ma taką samą jak on złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Podczas implementowania tego rozwiązania należy zapewnić miejsce w tablicy potrzebne do dodania wartownika. Należy więc deklarować tablicę o rozmiarze o jeden większym jak liczba przechowywanych elementów.
Przykład:
Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Dodajemy na końcu tablicy element o wartości 2, czyli a[6] = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, element znaleźliśmy pod indeksem 3, nie jest to ostatni element tablicy zatem znaleźliśmy szukany element.
Poszukajmy teraz element x = 5.
Dodajemy na końcu tablicy element o wartości 5, czyli a[6] = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
a[6] = x? 5 jest równe 5, element znaleźliśmy pod indeksem 6, jest to ostatni element tablicy zatem nie znaleźliśmy szukanego elementu a jedynie natrafiliśmy na naszego wartownika, który zabezpieczył nas przed wyjściem poza zakres tablicy. Werdykt zatem brzmi: elementu 5 nie ma w przeszukiwanej tablicy.
Jeżeli przyjrzymy się dokładnie klasycznemu algorytmowi przeglądania tablicy w poszukiwaniu elementu:
zauważymy, że dla każdego elementu wykonywane są dwa porównania:
- pierwsze: czy znaleźliśmy się już na końcu tablicy,
- drugie: czy aktualnie przeglądany element jest równy poszukiwanemu.
Liczbę porównań można zredukować wykorzystując algorytm wyszukiwania z wartownikiem. Nazwa tego algorytmu bierze się ze sposobu, w jaki wykorzystywany jest element szukany x.
By odnaleźć element x podejmiemy następujące kroki:
- na końcu tablicy (czyli pod indeksem n+1) wstawimy szukany element x - będzie to nasz wartownik, w przypadku gdy nie znajdziemy go nigdzie indziej w tablicy, zabezpieczy nas on przed wyjściem poza tablicę,
- przejdziemy po kolejnych elementach tablicy, tak długo aż nie znajdziemy szukanego elementu,
- w momencie znalezienia szukanego elementu x sprawdzamy, który jest to element tablicy? Jeżeli jest to ostatni element tablicy (n+1) to trafiliśmy na naszego wartownika i oznacza to, że w tablicy nie było szukanego elementu x, w przeciwnym razie element x został odnaleziony.
W stosunku do klasycznego algorytmu wyszukiwania oszczędzamy czas na sprawdzaniu czy osiągnęliśmy koniec tablicy. Sprawdzenie to występuje raz - po odnalezieniu elementu szukanego, a nie tak jak poprzednio przed każdym sprawdzeniem kolejnego elementu.
Operację odnajdowania elementu w tablicy z wartownikiem możemy zapisać następującym schematem blokowym:
Algorytm ten mimo, że jest szybszy od zwykłego wyszukiwania to ma taką samą jak on złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Podczas implementowania tego rozwiązania należy zapewnić miejsce w tablicy potrzebne do dodania wartownika. Należy więc deklarować tablicę o rozmiarze o jeden większym jak liczba przechowywanych elementów.
Przykład:
Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Dodajemy na końcu tablicy element o wartości 2, czyli a[6] = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, element znaleźliśmy pod indeksem 3, nie jest to ostatni element tablicy zatem znaleźliśmy szukany element.
Poszukajmy teraz element x = 5.
Dodajemy na końcu tablicy element o wartości 5, czyli a[6] = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
a[6] = x? 5 jest równe 5, element znaleźliśmy pod indeksem 6, jest to ostatni element tablicy zatem nie znaleźliśmy szukanego elementu a jedynie natrafiliśmy na naszego wartownika, który zabezpieczył nas przed wyjściem poza zakres tablicy. Werdykt zatem brzmi: elementu 5 nie ma w przeszukiwanej tablicy.
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | C# | MS Visual Studio .net |  | |
 / 0 |
| Tomasz Lubiński | C/C++ |  | |
 / 2 | |
| Marian | C/C++ | C++ | | |
/ 1 |
| Krzysztof Sośnierz | C/C++ | C++ templates | | |
/ 0 |
| Tomasz Lubiński | Delphi/Pascal |  | |
/ 0 | |
| Tomasz Lubiński | Java |  | |
/ 3 | |
| Dominik Goździuk | Php |  | |
/ 1 |
Poprawiony: czwartek, 26 maja 2011 20:54
Komentarze
Myślę że jeśli musisz znaleźć wszystkie to wtedy po znalezieniu elementu dodajesz do jakiejś tablicy w którym miejscu znajduje się szukany element, potem przechodzisz do warunku i=n+1 i jeśli i nie jest równe n+1 to wracasz do i = i+1. Nadal algorytm jest szybszy, bo warunek i=n+1 sprawdzasz tylko przy każdym wystąpieniu szukanej wartości a nie za każdym razem.