Andrew Hunt, Dav

[ Pobierz całość w formacie PDF ]
.W przypadku złożoności O(lg(n)) prawdopodobnie będziemymusieli poczekać 3 sekundy.Złożoność O(n) oznacza liniowy wzrost do 10 se-kund, a wykonywanie algorytmu o złożoności O(n lg(n)) zajęłoby około 33 sekun-dy.Jeśli nie mamy tyle szczęścia i nasza funkcja cechuje się złożonością O(n2),musimy przygotować się na oczekiwanie przez około 100 sekund.A jeśli po-sługujemy się algorytmem o złożoności wykładniczej O(2n), możemy spokojnieprzystąpić do parzenia kawy nasza funkcja powinna zakończyć działaniepo 10 263 latach.Wydaje się, że ludzkość nie ma tyle czasu.Notacja O() nie musi być stosowana tylko dla czasu równie dobrze można jejużywać do reprezentowania dowolnych innych zasobów używanych przez algo-rytm.Notacji O() często używa się do modelowania poziomu wykorzystania pa-mięci (patrz ćwiczenie 35.na końcu tego podrozdziału).196 u� Rozdział 6.Kiedy kodujemy&Szacowanie zdroworozsądkowePrzybliżoną złożoność wielu prostych algorytmów możemy szacować, posłu-gując się wyłącznie intuicją i zdrowym rozsądkiem.l� Proste pętle.Jeśli prosta pętla wykonuje od 1 do n-tej iteracji, złożonośćcałego algorytmu najprawdopodobniej wynosi O(n) czas jego wykony-wania rośnie liniowo wraz z wartością n.Do typowych przykładów należywyczerpujące wyszukiwanie, odnajdywanie wartości maksymalnej w ta-blicy oraz generowanie sum kontrolnych.l� Pętle zagnieżdżone.Jeśli zagnieżdżamy jedną pętlę w innej pętli, otrzy-mujemy algorytm o złożoności O(m�n), gdzie m oraz n to liczby iteracji obupętli.Taka sytuacja często ma miejsce w prostych algorytmach sortują-cych (na przykład w algorytmie sortowania bąbelkowego), gdzie pętlazewnętrzna przeszukuje wszystkie elementy tablicy, a pętla wewnętrznaokreśla, gdzie należy umieszczać każdy z tych elementów w posortowanejtablicy wynikowej.Takie algorytmy sortujące zwykle mają złożoność O(n2).l� Przeszukiwanie dwudzielne.Jeśli nasz algorytm dzieli na pół zbiór ele-mentów w każdym przebiegu pętli, złożoność tego kodu najprawdopo-dobniej jest logarytmiczna i wynosi O(lg(n)) (patrz ćwiczenie 37.na końcutego podrozdziału).Taką złożonością cechuje się wyszukiwanie binarnena posortowanej liście oraz odnajdywanie pierwszego ustawionego bituw słowie maszynowym.l� Dziel i zwyciężaj.Algorytmy, które dzielą swoje dane wejściowe i pracująniezależnie na dwóch połowach, po czym łączą wyniki, osiągają złożonośćO(n lg(n)).Klasycznym przykładem jest algorytm sortowania szybkiego,który dzieli dane na dwie połowy i rekurencyjnie sortuje każdą z nich.Mimo że formalnie wciąż mamy do czynienia z algorytmem O(n2), w prak-tyce algorytm działa szybciej, kiedy otrzymuje posortowane dane wejścio-we, zatem średnia złożoność sortowania szybkiego wynosi O(n lg(n)).l� Algorytmy kombinatoryczne.Każdy algorytm poszukujący permuta-cji oznacza ryzyko utraty kontroli nad czasami wykonywania.Problemw tym, że liczba permutacji jest równa silni liczby elementów (istnieje5! = 5�4�3�2�1 = 120 permutacji cyfr od 1 do 5).Oznacza to, że czaspotrzebny do przetworzenia przez algorytm kombinatoryczny pięciuelementów wydłuży się 6-krotnie w przypadku sześciu elementów oraz42-krotnie w przypadku siedmiu elementów.Tego rodzaju algorytmystosuje się do rozwiązywania trudnych obliczeniowo problemów, jakproblem komiwojażera, problem optymalnego rozmieszczania zawartościkontenera, dzielenie zbioru liczb tak, aby suma elementów w każdympodzbiorze była identyczna itp.Często stosuje się algorytmy heurystycz-ne, które pozwalają skrócić czas wykonywania tych algorytmów w kon-kretnych dziedzinach problemu.Szybkość algorytmu t� 197Szybkość algorytmu w praktyceTrudno oczekiwać, aby pisanie funkcji sortujących miało zająć istotną częśćnaszej kariery.Rozwiązania zaimplementowane już w dostępnych bibliotekachprawdopodobnie oferują wyższą wydajność niż jakikolwiek kod, który mogli-byśmy napisać w rozsądnym czasie.Okazuje się jednak, że podstawowe rodzajealgorytmów, które opisaliśmy wcześniej, w różnych formach przewijają sięw pracy każdego programisty.Za każdym razem, gdy piszemy prostą pętlę,możemy być pewni, że złożoność tego algorytmu wyniesie O(n) [ Pobierz całość w formacie PDF ]

Podobne