Wyszukiwanie liniowe

Przypomnijmy sobie najważniejsze informacje dotyczące algorytmu wyszukiwania liniowego.

Polega on na sprawdzaniu, czy kolejne elementy zbioru są szukaną liczbą. Możemy wyróżnić najprostszą wersję algorytmu oraz jego modyfikację – algorytm wyszukiwania liniowego z wartownikiemwartownikwartownikiem.

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów w tablicy tablica

• tablica – n-elementowa tablica liczb naturalnych

• szukana – liczba naturalna

Wynik:

• komunikat wskazujący indeks, pod którym znajduje się szukana liczba lub informujący, że w tablicy nie ma szukanej liczby

Wyszukiwanie liniowe bez wartownika

Zapiszmy nagłówek funkcji. Przyjmuje ona trzy argumenty – tablicę liczb, szukany element oraz liczbę elementów tablicy.

Na początku przypisujemy dwóm zmiennym pomocniczym odpowiednie wartości. Zmiennej znaleziono przypisujemy wartość fałsz, a zmiennej i wartość 0.

W kolejnym kroku zapisujemy pętlę dopóki. Będzie się ona wykonywać tak długo, jak długo będą spełnione dwa warunki – zmienna znaleziono będzie przechowywać wartość logiczną fałsz oraz wartość zmiennej i będzie mniejsza od długości tablicy, czyli wartości zmiennej n.

W pętli zapisujemy warunek logiczny jeżeli. Będziemy sprawdzać, czy wartość i-tego elementu tablicy jest równa szukanej liczbie  – jeżeli tak, wypiszemy odpowiedni komunikat, przypiszemy zmiennej znaleziono wartość prawda i zakończymy działanie algorytmu; jeżeli nie, zwiększymy wartość zmiennej i o 1.

W sytuacji, gdy po wyjściu z pętli dopóki wartością zmiennej znaleziono będzie fałsz, wypiszemy komunikat, że szukana liczba nie została znaleziona.

funkcja wyszukiwanie_liniowe(tablica, szukana, n)
    znaleziono ← fałsz
    i ← 0
    dopóki znaleziono != prawda oraz i < n wykonuj:
        jeżeli tablica[i] = szukana
            wypisz "Znaleziono liczbę na pozycji " + i
            znaleziono ← prawda
            zakończ działanie pętli
        i ← i + 1

    jeśli znaleziono = fałsz
        wypisz "Nie znaleziono szukanej liczby"

Operacjami, które najbardziej wpływają na złożoność tego algorytmu, są operacje porównania (wykonujące się w pętli dopóki). Dla n liczb może się ich wykonać, zależnie od ułożenia danych, od 1 do n, ponieważ w najgorszym wypadku musimy sprawdzić wszystkie liczby. Zatem złożoność czasowa tego algorytmu to $O\left(n\right)$.

Wyszukiwanie liniowe z wartownikiem

Wartownik dodajemy na początku lub na końcu tablicy. Zależnie od implementacji może to być zarówno liczba, która nie występuje w tablicy, jak i wartość szukana.

Przedstawimy wersję, w której wartownik jest szukaną liczbą. Umieścimy go na końcu tablicy.

Zapiszmy nagłówek funkcji. Ponownie przyjmuje ona trzy argumenty – tablicę liczb, szukany element oraz liczbę elementów tablicy.

Na początku umieszczamy wartownik na końcu tablicy, a zmiennej pomocniczej i przypisujemy wartość 0.

W kolejnym kroku zapisujemy pętlę dopóki. Będzie się wykonywać tak długo, jak długo wartość i-tego elementu tablicy będzie różna od szukanej liczby.

W każdej iteracji pętli będziemy zwiększać wartość zmiennej pomocniczej o 1.

Zapisujemy warunek logiczny jeżeli. Będziemy sprawdzać, czy wartość zmiennej i jest mniejsza od różnicy długości tablicy oraz liczby 1. Jeśli tak, wypiszemy odpowiedni komunikat mówiący o tym, że szukana liczba została znaleziona pod indeksem równym i. W przeciwnym wypadku wypiszemy komunikat mówiący o tym, że szukana liczba nie została znaleziona.

funkcja wyszukiwanie_liniowe_wartownik(tablica, szukana, n)
    tablica[n] ← szukana
    i ← 0

    dopóki tablica[i] != szukana wykonuj:
        i ← i + 1

    jeśli i < n - 1:
        wypisz "Znaleziono liczbę na pozycji " + i
    w przeciwnym przypadku:
        wypisz "Nie znaleziono szukanej liczby"

Ponownie operacjami, które najbardziej wpływają na złożoność tego algorytmu, są operacje porównania (wykonujące się w pętli dopóki). Może się ich wykonać, zależnie od ułożenia danych, od 1 do n. Zatem złożoność czasowa tego algorytmu to również $O\left(n\right)$. Zwróćmy jednak na to, że poprzez dodanie wartownika wyeliminowaliśmy konieczność sprawdzania przy każdym kolejnym elemencie, czy nie przekroczyliśmy rozmiaru tablicy – zredukowaliśmy zatem liczbę instrukcji.

Wyszukiwanie binarne

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów tablicy tablica

• tablica – n-elementowa tablica liczb naturalnych

• szukana – liczba naturalna

Wynik:

• komunikat wskazujący indeks, pod którym znajduje się szukana liczba, lub informujący, że w tablicy nie ma szukanej liczby

Algorytm wyszukiwania binarnego wyszukuje wybrany element w posortowanym w zbiorze. W e‑materiale Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”Pv0IXD75RRozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj” przedstawiliśmy jego wersję rekurencyjną.

W tym e‑materiale skupimy się na jego iteracyjnej wersji.

Zasada działania algorytmu nie zmienia się. Algorytm nie wywołuje się rekurencyjnie, wykorzystujemy natomiast pętlę dopóki.

Zapisujemy nagłówek funkcji wyszukiwanie_binarne_iter. Przyjmie ona cztery argumenty – tablicę liczb, szukaną wartość, indeks początku oraz indeks końca.

W kolejnym kroku określimy środek analizowanego przedziału, przypisując zmiennej środek wartość dzielenia całkowitego sumy wartości zmiennych pocz oraz kon przez liczbę 2.

Następnie zapiszemy instrukcję warunkową jeżeli. Sprawdzamy, czy szukana liczba jest równa wartości elementu tablicy o indeksie równym wartości zmiennej środek. Jeśli tak, wypisujemy odpowiedni komunikat.

Jeśli element nie jest równy elementowi przechowywanemu pod indeksem środek, sprawdzamy, czy jest on od niego mniejszy. Jeśli tak, zmieniamy wartość zmiennej pocz, przypisując jej wartość sumy zmiennej środek oraz liczby 1.

Jeżeli element jest mniejszy, przypisujemy zmiennej kon wartość różnicy zmiennej środek oraz liczby 1.

Jeśli po wyjściu z pętli dopóki element nie został znaleziony, wypisujemy odpowiedni komunikat.

funkcja wyszukiwanie_binarne_iter(tablica, szukana, pocz, kon):
	dopóki pocz <= kon:
    	środek ← (pocz + kon) div 2     
    	jeżeli tablica[środek] = szukana:
    		wypisz "Znaleziono liczbę na pozycji " + środek
            zwróć środek
    	w przeciwnym wypadku jeżeli tablica[środek] < szukana:
    		pocz = środek + 1
    	w przeciwnym wypadku:
    		kon = środek - 1
            
	wypisz "Nie znaleziono szukanej liczby"

Algorytm wyszukiwania binarnego działa przez podział zakresu wyszukiwania na dwie równe części i wybór tej, która zawiera szukaną wartość (lub może ją zawierać). Dzięki temu zakres wyszukiwania jest dzielony na pół w każdej iteracji. W konsekwencji każdy podział sprowadzi problem do problemu o połowę mniejszego.

W związku z tym, jeżeli mamy tablicę o długości $n$, to w najgorszym wypadku potrzebujemy $O\left(\log n\right)$ podziałów, aby zawęzić zakres wyszukiwania do jednego elementu. Stąd złożoność czasowa wynosi $O\left(\log n\right)$.

Lider w zbiorze

Czym jest liderliderlider? Określamy tak liczbę, która występuje w zbiorze n-elementowym więcej niż $\frac{n}{2}$ razy. Ponieważ jedna liczba nie może występować w tym samym zbiorze liczbowym więcej niż $\frac{n}{2}$ razy, lider jest tylko jeden.

Na przykład w zbiorze {1, 4, 6, 1, 1} lider to liczba 1, ponieważ występuje w nim aż 3 razy.

Natomiast w zbiorze {8, 6, 4, 5, 2, 2} żadna z sześciu liczb nie jest liderem, choć liczba 2 występuje więcej razy niż pozostałe.

Zbiory, które mają lidera, posiadają bardzo ważną właściwość: jeżeli z takiego zbioru usuniemy parę różnych liczb, zbiór ten nadal będzie miał tego samego lidera.

Rozważmy dwa przypadki.

Pierwszy dotyczy usunięcia pary liczb, z której żadna nie jest liderem. Ze zbioru {1, 4, 6, 1, 1} usuwamy liczby 4 oraz 6 i zostajemy z podzbiorem {1, 1, 1}. Ponieważ zbiór ten składa się tylko z jedynek, bardzo łatwo stwierdzić, że lider tego zbioru nie zmienił się i nadal jest nim liczba 1.

W drugim przypadku usuniemy jedną liczbę, która nie jest liderem, i jedną, która nim jest – czyli usuniemy liczby 4 oraz 1. Zostajemy wtedy ze zbiorem {1, 6, 1}, którego liderem nadal jest liczba 1. Ponieważ para, która zostaje wyeliminowana, nie może składać się z tych samych liczb, przypadek, w którym usunięte zostaną dwie liczby lidera, nie zaistnieje.

Algorytm wyboru lidera

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów zbioru zbiór

• zbior – zbiór liczb naturalnych

Wynik:

• komunikat wskazujący lidera zbioru lub informujący, że zbiór nie ma lidera

Przykład będzie bazował na zbiorze trzyelementowym, ponieważ łatwiej będzie na nim wskazać pewne zależności.

Wykorzystamy poznaną zależność.

Załóżmy, że pierwsza liczba ze zbioru jest liderem, oraz stwórzmy zmienną, która będzie liczyć wystąpienia lidera. Nazwijmy ją licznik. Skoro zakładamy, że pierwsza liczba jest liderem, zmienną licznik inicjalizujemy wartością 1, ponieważ jedno wystąpienie potencjalnego lidera już nastąpiło. Dodajemy również zmienną, która będzie przechowywała liczbę elementów zbioru.

W pseudokodzie będzie to wyglądało następująco:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

Następnym krokiem będzie iteracja przez cały zbiór. Ponieważ zakładamy, że pierwszy element zbioru jest liderem, i został on już uwzględniony w zmiennej licznik, możemy go pominąć w pętli i zainicjować zmienną sterującą wartością 1.

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,... n - 1 wykonuj
   

Naszym celem jest eliminacja par liczb, które nie są takie same. W konsekwencji, jeżeli kolejny element zbioru nie jest taki sam jak dotychczasowy lider (czyli poprzedni element), zmniejszymy wartość zmiennej licznik o jeden. W kolejnej iteracji sprawdzimy, czy zmienna licznik ma wartość 0. Jeżeli warunek jest prawdziwy, przesuniemy lidera na miejsce sprawdzanego elementu, ponieważ oznacza to, że para, która została sprawdzona, zawierała dwie różne liczby – może zatem zostać pominięta. Zobaczmy, jak będzie to wyglądać w pseudokodzie, a następnie przetestujmy działanie tej części algorytmu na przykładzie:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,... n - 1 wykonuj
	jeżeli licznik > 0 to
		jeżeli lider ← zbior[i] to
			licznik ← licznik + 1
		w przeciwnym wypadku
			licznik ← licznik - 1
	w przeciwnym wypadku
		lider ← zbior[i]
		licznik ← 1

Dla przykładu rozważmy zbiór {1, 3, 1, 3, 1, 3, 1}, w którym liderem jest 1, i przeanalizujmy działanie algorytmu.

zbior ← {1, 3, 1, 3, 1, 3, 1}
lider ← 1
licznik ← 1
n ← 3

Wchodzimy w pętlę for, zmienna sterująca i otrzymuje wartość 1. Zmienna licznik ma wartość 1, więc jest większa niż 0.

Czy lider jest równy zbior[i]? Podstawmy wartości i sprawdźmy.

Po podstawieniu wartości wiemy, że wartości tych zmiennych nie są sobie równe.

Odejmujemy od zmiennej sterującej 1 i przechodzimy do kolejnej iteracji. Zmienna licznik jest równa 0, więc przenosimy lidera do zbior[2] czyli 1, a zmiennej licznik przypisujemy wartość 1. Dzięki temu pierwsza para (1, 3) zostaje usunięta, ponieważ liczby w tej parze nie są takie same.

Co się jednak dzieje, gdy para zawiera te same liczby? Ponieważ liczba powtórzyła się, zostaje kandydatem na lidera. Zwiększamy więc wartość zmiennej licznik, która liczy liczbę wystąpień potencjalnego lidera.

W rezultacie działania pętli otrzymamy potencjalnego lidera oraz zmienną licznik. Jeżeli wartość zmiennej licznik wynosi 0, badany zbiór nie ma lidera. Aby mieć pewność, że potencjalny lider jest faktycznie liderem, policzymy liczbę jego wystąpień w zbiorze i sprawdzimy, czy liczba ta jest większa niż długość zbioru podzielona na 2. Dodajmy te zmiany do algorytmu:

zbior ← {1, 3, 1}
lider ← zbior[0]
licznik ← 1
n ← 3

dla i = 1, 2,...n - 1 wykonuj
	jeżeli licznik > 0 to
		jeżeli lider = zbior[i] to
			licznik ← licznik + 1
		w przeciwnym wypadku
			licznik ← licznik - 1
	w przeciwnym wypadku
		lider ← zbior[i]
		licznik ← 1

jeżeli licznik = 0 to
	wypisz "Zbiór nie ma lidera"
	zakończ działanie programu
  
liczba_wystapien_lidera ← 0
dla i = 0, 1,...n - 1 wykonuj
	jeżeli zbior[i] = lider to
		liczba_wystapien_lidera = liczba_wystapien_lidera + 1
    
jeżeli liczba_wystapien_lidera > n / 2 to
	wypisz "Liderem zbioru jest " + lider
w przeciwnym wypadku
	wypisz "Zbiór nie ma lidera"

Dominującymi operacjami w omawianym rozwiązaniu są porównania w pętlach wykonujących się dla każdego elementu zbioru wejściowego, a zatem złożoność czasowa algorytmu wynosi $O\left(n\right)$.

Kim jest idol w zbiorze?

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba osób

• znajomosci – tablica o wymiarach n × n; przechowuje liczby naturalne 0 oraz 1; tablica informacji na temat tego, które osoby się znają

Wynik:

• komunikat wskazujący lidera zbioru lub informujący, że zbiór nie ma idolaidolidola

Na przyjęciu znajduje się n osób. Osoby oznaczone są numerami od $0$ do $n-1$. Ponieważ jest to duża impreza, nie wszyscy goście się znają. Osoba A może znać osobę B, co niekoniecznie musi oznaczać, że osoba B zna osobę A. Może się okazać, że na przyjęciu pojawiła się osoba na tyle popularna, że jest znana przez wszystkich. Jeżeli ponadto okaże się, że osoba ta nie zna nikogo spośród pozostałych gości, możemy nazwać ją idolem.

Poniżej zaprezentowano dwuwymiarową tablicę typu logicznego, która określa stan znajomości wśród osób znajdujących się na przyjęciu. Jeżeli wartość znajomość[A][B] wynosi 1 (zauważmy, że to tablica liczb całkowitych, nie tablica boolowska), to przyjmujemy, że osoba A zna osobę B. Dla porządku przyjmujemy, że dana osoba nie zna siebie samej.

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

Zastanówmy się, ile pytań „Czy osoba A zna osobę B?” musimy zadać, aby sprawdzić, czy na przyjęciu pojawił się idol oraz kto nim jest.

Spróbujmy dokładnie przeanalizować informację, która wynika z odpowiedzi na pojedyncze pytanie: „Czy osoba A zna osobę B?” w kontekście wyszukiwania idola. Ponieważ idol jest osobą, która musi być znana przez każdego oraz sama nie może znać nikogo, wymienione wyżej pytanie pozwala nam stwierdzić, która z osób A lub B na pewno nie jest idolem. Jeżeli odpowiedź na nie brzmi twierdząco, wiemy, że osoba A nie może być idolem, ponieważ zna przynajmniej jedną osobę. Jeśli odpowiedź jest przecząca, to z kolei osoba B nie może być uznana za idola, ponieważ istnieje przynajmniej jedna osoba, która jej nie zna.

Tym sposobem możemy wyznaczyć idealnego kandydata na idola, zadając tylko $0$ do $n-1$ pytań. Zapiszmy ten proces w postaci pseudokodu:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]
kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat = i

Następnie sprawdzimy, czy wyznaczony kandydat może być idolem. W tym celu musimy przepytać wszystkich gości, czy znają wyznaczonego kandydata, a także przepytać kandydata, czy nie zna nikogo. Każdy z tych procesów będzie składał się z zadania $n-1$ pytań.

Do wcześniejszego pseudokodu dopiszemy linijki odpowiadające za sprawdzenie, czy wyznaczony kandydat jest idolem:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// przepytaj gości, czy znają kandydata
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy osoba i nie jest kandydatem
	jeżeli kandydat != i to
    	// sprawdź, czy osoba i zna kandydata
    	jeżeli !znajomość[i][kandydat] to
        	// osoba i nie zna kandydata
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ działanie pętli

// przepytaj kandydata, czy nie zna gości
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź, czy kandydat nie jest osobą i
	jeżeli kandydat != i to
        // sprawdź, czy kandydat nie zna osoby i
    	jeżeli znajomość[kandydat][i] to
        	// kandydat zna osobę i
            // kandydat nie jest idolem
            // idol nie istnieje
        	wypisz "Idol nie istnieje"
            zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Powyższy kod można skrócić, wykorzystując podobieństwo dwóch pętli:

n ← 5
znajomość[n][n] ← [
	[ 0, 1, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1 ],
    [ 0, 1, 0, 1, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 0 ]
]

kandydat ← 0

dla i = 1, 2, ..., n - 1 wykonuj
	jeżeli znajomość[kandydat][i] to
    	kandydat ← i
    // w przeciwnym wypadku kandydat dalej może być idolem

// sprawdź, czy kandydat jest idolem
dla i = 0, 1, ..., n - 1 wykonuj
	// sprawdź czy nie pytamy kandydata o samego siebie
    // oraz czy czy osoba i zna kandydata
    // oraz czy kandydat nie zna osoby i
	jeżeli kandydat != i
    	oraz !znajomość[i][kandydat]
        oraz znajomość[kandydat][i] to
        // osoba i nie zna kandydata
        // lub kandydat zna osobę i
        // kandydat nie jest idolem
        // idol nie istnieje
        wypisz "Idol nie istnieje"
        zakończ wykonywanie programu

wypisz "Idolem jest osoba numer " + kandydat

Przedstawiony algorytm pozwala nam na znalezienie idola po zadaniu $3\left(n-1\right)$ pytań.

By to uzasadnić, przypomnijmy jak działa omówiony algorytm. Najpierw sprawdzamy, czy każda kolejna osoba (poza pierwszą) zna obecnego kandydata (czyli pierwszą osobę). Daje to $n-1$ pytań.

Następny krok wymaga sprawdzana, czy kolejne osoby z grupy znają kandydata (czyli znowu zadajemy $n-1$ pytań) oraz czy kandydat zna te kolejne osoby (kolejne $n-1$ pytań).

By znaleźć idola zadajemy $3\left(n-1\right)$ pytań. To oznacza, że złożoność czasowazłożoność czasowazłożoność czasowa omówionego algorytmu wynosi $O\left(n\right)$.

Słownik