Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”
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 szybkiesortowanie szybkie (quick sort) oraz sortowanie przez scalaniesortowanie przez scalanie (merge sort), wyszukiwanie binarnewyszukiwanie binarne.
Więcej wskazówek dotyczących rozwiązywania problemów informatycznych znajdziesz w e‑materiałach:
Projektowanie algorytmów: metody wstępująca i zstępującaProjektowanie algorytmów: metody wstępująca i zstępująca,
Jak myśleć komputacyjnie?Jak myśleć komputacyjnie?,
Rozwiąż to inaczej, czyli myślenie komputacyjne i jego metodyRozwiąż to inaczej, czyli myślenie komputacyjne i jego metody.
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.