R1eHgRpwGtmJN
Zdjęcie przedstawia drewniany blat, na którym stoi otwarty laptop w białej obudowie. Widoczne są ręce siedzącego przy nim człowieka w koszuli w niebiesko - czerwoną kratę oraz uniesione w górę dłonie. W tle rozmyta postać kobiety zwróconej profilem z czarnymi włosami, ubranej w jasnoszary sweter.

Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”

Źródło: Headway, domena publiczna.

Strategię „dziel i zwyciężaj” wykorzystujemy w sytuacji, gdy chcemy, aby zastosowany algorytm miał możliwie małą złożoność czasową. Metoda ta polega na dzieleniu problemu na mniejsze części, by jak najefektywniej rozwiązać problem główny.

Przykładami algorytmów sortowania opartych na strategii „dziel i zwyciężaj” są np. sortowanie szybkiePpzx1Yyemsortowanie szybkie (quick sort) oraz sortowanie przez scalaniePNHdnGJ4Isortowanie przez scalanie (merge sort), wyszukiwanie binarnePiVb7f8s2wyszukiwanie binarne.

Więcej wskazówek dotyczących rozwiązywania problemów informatycznych znajdziesz w e‑materiałach:

Twoje cele
  • Prześledzisz etapy realizacji strategii „dziel i zwyciężaj”.

  • Przeanalizujesz przykładowe algorytmy, w których zastosowano strategię „dziel i zwyciężaj”.

  • Wyjaśnisz, w jakich okolicznościach warto zastosować metodę „dziel i zwyciężaj”.

  • Przeanalizujesz złożoność czasową algorytmu opartego na strategii „dziel i zwyciężaj”.

  • Przeanalizujesz algorytm jednoczesnego wyszukiwania minimum i maksimum.