|
|
Zasada dziel i zwyciężaj (ang. divide and conquer principle) |
Ważne definicje:
Algorytmy sortowania:
|
Metoda projektowania algorytmów. Polega na podziale problemu na mniejsze problemy, które na ogół są tym samym problemem, ale dla danych o mniejszych rozmiarach, i przezwyciężeniu go w ten sposób. Niewielkie powiązania między podproblemami powodują, że łatwo jest złożyć rozwiązania podproblemów w rozwiązanie problemu. Przykładem takiego podejścia jest np. algorytm porządkowania, w którym na każdym kroku ciąg jest dzielony na dwie części, elementy w tych częściach są porządkowane, a następnie już uporządkowane części są łączone w jedną uporządkowaną całość. Taki charakter mają sortowanie przez scalanie i szybkie sortowanie. Szczególnym przypadkiem tej metody jest strategia, w której na każdym kroku rozwiązywania problemu jest on dzielony na co najmniej dwie części i do dalszych obliczeń pozostaje tylko jedna z nich. Przykładem takiego działania jest poszukiwanie elementu (lub miejsca dla niego) w ciągu uporządkowanym – jest to tzw. poszukiwanie przez połowienie, często stosowane w słownikach i encyklopediach. Algorytmy oparte na tej zasadzie charakteryzują się często bardzo dobrą, czyli niską złożonością obliczeniową – stąd właśnie owo zwycięstwo w nazwie tej metody. Według zasady "dziel-i-zwyciężaj" są często budowane algorytmy rekurencyjne. Tej zasady nie należy mylić ze starożytną maksymą łacińską divide et impera (pol. dziel-i-rządź), która również zaleca dzielenie "substancji", nad którą należy zapanować, ale w tym podziale im gorsza jest komunikacja między wydzielonymi częściami, tym lepiej. Literatura
|
Strona główna Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez binarne wstawianie Sortowanie przez wybór Sortowanie przez scalanie Sortowanie przez scalanie - rozszerzone Sortowanie szybkie Sortowanie stogowe Sortowanie stogowe rozszerzone Porównanie algorytmów
