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 (kandydaci na max) i (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. 

  1. #include<iostream>
  2. #include<ctime>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. int T[1000005];
  7. int M[500005];
  8. int D[500005];
  9.  
  10. void Dziel(int n);
  11.  
  12. int main()
  13. {
  14.         int a,n;
  15.         cin>>n;
  16.         for (int i=0;i<n;i++)
  17.                 cin>>T[i];             
  18.         Dziel(n);      
  19.        
  20.         cout<<"\nD:\n";
  21.         for (int i=0;i<n;i++)
  22.                 cout<<D[i]<<" ";
  23.         cout<<"\nM:\n";
  24.         for (int i=0;i<n;i++)
  25.                 cout<<M[i]<<" ";
  26. }
  27.  
  28.  
  29. void Dziel(int n)
  30. {
  31.         for (int i=1;i<n;i+=2)
  32.         {
  33.                 if (T[i]>T[i-1])
  34.                         {
  35.                                 D[i/2]=T[i]; M[i/2]=T[i-1];
  36.                         }
  37.                         else
  38.                         {
  39.                                 M[i/2]=T[i]; D[i/2]=T[i-1];
  40.                         }                      
  41.         }
  42.         if (n%2==1)
  43.         {
  44.                 M[n/2]=T[n-1]; D[n/2]=T[n-1];
  45.         }
  46. }
  47.