Разделяй и властвуй или как решать большие задачи

• Человечество решает сложные задачи, разбивая их на более простые и решая их по отдельности.  

• Принцип разделяй и властвуй позволяет упростить сложные задачи, разбивая их на под-задачи и решая их последовательно.  

• Определение палиндрома в связанном списке.  

• Возведение в степень.  

• Декодирование строки или парсинг булевого выражения.  

• Номер страницы в экселе.  

• Рекурсия - это решение под-задачи как исходной задачи.  

• Рекурсия может быть медленной, иногда стоит заменить ее циклом и стеком.  

• Примеры шуток про рекурсию.  

• Разделение массива на две части и сортировка каждой части отдельно.  

• Объединение отсортированных частей в итоговый отсортированный массив.  

• Реализация функции слияния двух отсортированных массивов.  

• Использование логарифмического объема памяти для сортировки массива.  

• Объединяем массив во временный массив, затем копируем значение из временного массива в основной.  

• Рекурсивно находим максимальную сумму подмассива для левой и правой половин.  

• Находим максимальную сумму пересечения двух подмассивов.  

• Разделяем массив на две половины, находим количество инверсий в каждой половине.  

• Сортируем каждую половину, находим количество инверсий в пересечении двух отсортированных половин.  

• Находим количество инверсий, где левое число минимум в два раза больше правого.  

• Находим элемент, который находился бы на каждой позиции начала или конца, если отсортировать массив.  

• Задача состоит в том, чтобы найти элемент, который находится на определенном месте в массиве, без сортировки.  

• Разбиваем массив на три части: элементы меньше опорного, равные опорному и больше опорного.  

• Если к меньше или равно длине массива, то нужный элемент находится в массиве меньше опорного.  

• Если к больше, но меньше или равно сумме длин массивов меньше опорного и больше опорного, то элемент находится в массиве больше опорного.  

• Если к больше суммы длин массивов меньше опорного и больше опорного, то элемент находится в массиве меньше опорного.  

• Функция партишин разбивает массив на три части без дополнительных затрат по памяти.  

• Функция шафл перемешивает элементы в массиве.  

• Быстрая сортировка может быть применена к функции партишин для оптимизации.  

• Умножение чисел в столбик, умножение каждой цифры второго числа на каждую цифру первого числа.  

• Время работы порядка от n^2.  

• Разбиение задачи на несколько подзадач, решение подзадач, объединение ответов.  

• Время работы рекурсивной функции равно времени выполнения выделенного узла плюс время выполнения рекурсивных вызовов.  

• Видео объясняет геометрическую прогрессию и ее влияние на время выполнения рекурсивных алгоритмов.  

• Асимптотика времени выполнения алгоритма зависит от сложности задачи, коэффициента понижения сложности и степени сложности.  

• Асимптотика времени выполнения алгоритма умножения двух n-значных чисел с разбиением на четыре умножения n/2-значных чисел равна n^2.  

• Разделение задачи на подзадаче может быть недостаточно для ускорения алгоритма.  

• Алгоритм умножения Карацубы экономит на одном из восьми рекурсивных вызовов, позволяя получить время работы от n степени логарифм от 3 по основанию 2.  

• Используется в Пайтоне для перемножения чисел с количеством разрядов больше 70.  

• В видео обсуждается простой способ поиска множественных коллизий в игре, который заключается в проверке каждого объекта с каждым другим.  

• Этот метод требует порядка у тен квадрат времени для проверки всех объектов.  

• В видео предлагается разделить область на две половины и искать пересечение в каждой из них.  

• Это позволяет ускорить поиск коллизий, но требует дополнительного кода для разбиения области на квадраты и перераспределения объектов.  

• В видео подробно описывается реализация обнаружения коллизий, которая включает в себя проверку коллизий внутри квадратов и на границах квадратов.  

• Это позволяет значительно ускорить поиск коллизий и увеличить количество кадров в секунду.  

• В видео рассматривается задача Ханойской башни, которая заключается в переносе пирамиды из n колец на другой стержень за наименьшее число ходов.  

• Решение этой задачи основано на использовании структуры данных стек и рекурсивном алгоритме.  

• В заключение видео автор призывает ставить большие цели, разбивать их на части и не пытаться сделать все за раз.  

• Новый год - это время чудес, и программирование может помочь в достижении этих чудес.