Разделяй и властвуй — это алгоритмическая техника, в которой мы решаем задачу, разбивая её на меньшие подзадачи, решая эти подзадачи рекурсивно, а затем объединяя их ответы.
Типичный алгоритм «разделяй и властвуй» следует трём основным шагам:
Эта идея встречается во многих важных алгоритмах.
Дан массив
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
из чисел, отсортируйте массив за
времени, используя технику «разделяй и властвуй».
Реализуем функцию sort(a), которая принимает массив и возвращает его в отсортированном порядке.
Идея следующая:
1 или 0, он уже отсортирован, поэтому мы просто возвращаем его.и разделим массив на две части:
Затем мы рекурсивно сортируем обе части и сохраняем результаты в L и R.
Наконец, поскольку L и R уже отсортированы, мы можем слить их в один отсортированный массив за линейное время.
vector<int> sort(vector<int> a) {
if (a.size() <= 1) {
return a;
}
int m = a.size() / 2;
vector<int> L = sort(vector<int>(a.begin(), a.begin() + m));
vector<int> R = sort(vector<int>(a.begin() + m, a.end()));
vector<int> res;
merge(L.begin(), L.end(), R.begin(), R.end(), back_inserter(res));
return res;
}