Metoda dziel i zwyciężaj

Wpisany przez Michał Knasiecki

poniedziałek, 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: poniedziałek, 15 sierpnia 2005 23:53

Komentarze

+2 # 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ć

+1 # 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ć

0 # 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ć

Dodaj komentarz

JComments

	C/C++
	C#
	Delphi/Pascal
	Java
	Java Script
	Python
	Php
	Inny