search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

D04.6. Examples of algorithms that use the Divide and Conquer approach? #60

Open Balukova opened 4 years ago

Balukova commented 4 years ago

D04.6. Приклади алгоритмів, що використовують підхід Divide and Conquer?

Balukova commented 4 years ago

Було обговорено під час лекції: Merge sort, quick sort, binary search

chihh commented 4 years ago

Також пардигма Divide and Conquer використовується у таких алгоритмах як: бінарний пошук, алгоритм Штрассена, а також алгоритм Карацуби для швидкого множення, детальніше саме про ці алгоритми можна прочитати за посиланням https://www.geeksforgeeks.org/divide-and-conquer-algorithm-introduction/

bastikk commented 4 years ago

Потрібно також згадати про такі алгоритми як: -алгоритм пошуку двох точок. https://en.wikipedia.org/wiki/Closest_pair_of_points_problem -метод рекурсивного спуску(один з найпростіших алгоритмів парсингу). https://en.wikipedia.org/wiki/Parsing -алгоритм обчислення швидкого перетворення Фур'є. https://en.wikipedia.org/wiki/Fast_Fourier_transform

DmytroTarasov commented 4 years ago

I’ll move away a bit from the topic and say that the Tower of Hanoi, a classic problem, can be easily solved with a recursive "divide-and-conquer" algorithm. You can read about this topic, for example, here: https://web.eecs.umich.edu/~aprakash/eecs282/lectures/11-recursion.pdf

LavorM commented 4 years ago

Розділяй та володій (Divide and Conquer) це парадигма програмування, фактично, якщо алгоритм має логарифмічну складність (O(log n)), то він використовує цей метод (найчастіше він використовується для скорочння перебору і пришвидшення роботи алгоритмів)