algorytm.org

Metoda dziel i zwyciężaj



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda dziel i zwyciężaj
Ocena użytkowników:***** / 101
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 22:20

Jeżeli problem można podzielić na kilka mniejszych, niezależnych podproblemów i rozwiązać je rekurencyjnie a na końcu połączyć je w rozwiązanie całego problemu, możemy zastosować metodę "dziel i zwyciężaj". Ta metoda jest często stosowana, np. w algorytmie sortowania szybkiego lub binarnego wyszukiwania elementu w posortowanej tablicy.
Zobacz przykład sortowanie QuickSort

Poprawiony: 15 sierpnia 2005 23:53
Komentarze
photo
+31 # Geding 2010-01-18 16:59
Wydawałoby się że artykuł ma wytłumaczyć czym jest ta metoda a nie powiedzieć nam do czego ona się przydaje..
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Volkosky 2010-04-11 20:25
Ta metoda to dzielenie dużego problemu na mniejsze. Wyobraź sobie, że musisz znaleźć konkretną wartość w posortowanej tablicy. Jednym warunkiem sprawdzasz, w której połówce tablicy się ona znajduje i już masz połowę mniej roboty.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # kleer94 2011-06-20 01:17
Czytałem, że tą metodą są przeszukiwane rekordy w MySQL i zapewne nie tylko.
Polegało to na tym, że baza danych nie przegląda wszystkich rekordów po kolei lecz od razu wlatuje w środek tabeli. Jeżeli szukane id jest np. mniejsze od tego, w którego wlecono to znowu celuje w środek górnej połówki itd. aż do znalezienia szukanego id.
Jest to bardzo pomocne przy dużej np. 10000+ rekordów.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # JSx9nohny 2014-12-12 12:31
Bazy danych mają budowę drzwiastą,taka organizacja redukuje złożoność obliczeniową.Jeśli szukam czegoś na B to nie interesuje mnie C i D,więc skaczę tylko do jednego drzewa rekoprdów,a nie przeszukuje miliarda rekordów,wyobra żcie sobie jak działał by Facebook czy Google
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # nobody 2016-01-26 15:04
akurat przykład z Facebook i Google nietrafiony, tam są stosowane zupełnie inne bazy, nie uraczysz SQL ;)
natomiast co do budowy drzewiastej baz SQL - dotyczy to indeksów
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # JSx9nohny 2014-12-12 12:34
Charakterystyka tej metody to rozbijanie dużego zadania na mniejsze zadania,tak jak tu tablica jest rozbijana na fragmenty
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz