« poprzedni punkt | następny punkt » |
W tym wykładzie omówimy problem wyszukiwania w skończonym ciągu, przy założeniu, że dane zostały umieszczone w jednowymiarowej tablicy. Przedstawimy dwa warianty tego problemu: gdy ciąg jest uporządkowany i, gdy ciąg jest całkowicie dowolny. W obu przypadkach rozpoczniemy od omówienia algorytmów sekwencyjnych. Ponieważ te naiwne algorytmy są bardzo proste, pozwoli nam to skupić się na analizie poprawności, a dokładniej na zastosowaniu metody niezmiennika przy dowodzeniu poprawności tych algorytmów względem zadanej specyfikacji. Przeanalizujemy też dokładnie koszt tych algorytmów i da nam to okazję do analizy kosztu średniego, którego badanie zwykle nastręcza więcej trudności niż oszacowanie kosztu w przypadku pesymistycznym. Dla problemu wyszukiwania w ciągu uporządkowanym, przedstawimy ponadto dwa inne algorytmy. Pierwszy jest niewielkim usprawnieniem algorytmu sekwencyjnego. Jego koszt jest wprawdzie mniejszy niż koszt algorytmu sekwencyjnego, jednak rząd funkcji kosztu jest nadal liniowy. Drugi, algorytm binarnych poszukiwań, stosuje w specjalny sposób strategię "dziel i zwyciężaj" i rozwiązuje problem wyszukiwania w ciągu uporządkowanym z kosztem logarytmicznym, w stosunku do rozmiaru danych. Jest to istotna poprawa w porównaniu z poprzednimi algorytmami. Co więcej, algorytm ten jest optymalny w klasie algorytmów rozwiązujących problem wyszukiwania przez porównywanie elementów.
« poprzedni punkt | następny punkt » |