Poniższy program prezentuje możliwość wykorzystania metody dziel i zwyciężaj przy jednoczesnym poszukiwaniu wartości min i max w ciągu liczbowym.
Podczas tradycyjnego poszukiwania min i max w zbiorze musimy wykonać n porównań dla min oraz n porównań dla max -> stąd ilość opracji potrzebna do wykonania zadania wynosi O=n+n=2n;
Dziel i zwyciężaj
Przy wykorzyatniu metody dziel i zwycięzaj, w pierwszym przebiegu pętli przeglądamy sąsienie pary liczb ( pierwsza z drugą, trzecia z czwartą itd...), w każdym przypadku większa liczba trafia do tablicy D, a druga do tablicy M. Czyli w pierwszym przebiegu pętli program wykona n/2 operacji porównań (za każdym razem porównujemy dwie liczby, a licznik pętli przesuwa się o 2).
Do tego momentu nasz program wykonał n/2 operacji porównań.
Teraz kolej na przeszukanie zbiorów D (kandydaci na max) i M (kandydaci na min). Oba zbiory mają rozmiar n/2 (w przypadku parzystago n - dla nieparzystego n -> n/2+1). Przeszukanie możemy wykonać metodą tradycyjną (w każdym zbiorze poszukujemy tylko jednej wartości - większej(D) lub mniejszej(M)).
Przeszukanie zbioru D to n/2 operacji, podobnie ze zbiorem M.
Stąd liczba wykonanych operacji przy wykorzyatniu metody dziel i zwyciężaj wynosi O=n/2+n/2+n/2=(3/2)n
Wniosek - wykorzystując metodę dziel i zwyciężaj zaoszczędziliśmy n/2 (2n-3n/2) operacji (czyli dla zbioru o rozmiarze n=1000 program wykona 500 operacji mniej - 1500 zamiast 2000).
Poniższy kod prezentuje efekt podzielenia zbioru na dwa nowe zbiory - D i M.
-
#include<iostream>
-
#include<ctime>
-
#include<algorithm>
-
using namespace std;
-
-
int T[1000005];
-
int M[500005];
-
int D[500005];
-
-
void Dziel(int n);
-
-
int main()
-
{
-
int a,n;
-
cin>>n;
-
for (int i=0;i<n;i++)
-
cin>>T[i];
-
Dziel(n);
-
-
cout<<"\nD:\n";
-
for (int i=0;i<n;i++)
-
cout<<D[i]<<" ";
-
cout<<"\nM:\n";
-
for (int i=0;i<n;i++)
-
cout<<M[i]<<" ";
-
}
-
-
-
void Dziel(int n)
-
{
-
for (int i=1;i<n;i+=2)
-
{
-
if (T[i]>T[i-1])
-
{
-
D[i/2]=T[i]; M[i/2]=T[i-1];
-
}
-
else
-
{
-
M[i/2]=T[i]; D[i/2]=T[i-1];
-
}
-
}
-
if (n%2==1)
-
{
-
M[n/2]=T[n-1]; D[n/2]=T[n-1];
-
}
-
}
-
