Разделяй и властвуй (программирование)
- Разделяй и властвуй (программирование)
-
Разделяй и властвуй (англ. divide and conquer) — в информатике важная парадигма разработки алгоритмов. Основана на рекурсивном разбиении решаемой задачи на две (или более) подзадачи того же типа, но меньшего размера. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Типичный пример — Quicksort. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока не останется отсортировать массивы длины 1 или 2. Время выполнения этого алгоритма в среднем пропорционально nlogn, тогда как более простые алгоритмы дают n², где n — размер исходного массива.
Литература
Ссылки
Wikimedia Foundation.
2010.
Смотреть что такое "Разделяй и властвуй (программирование)" в других словарях:
Разделяй и Властвуй — Разделяй и властвуй: Разделяй и властвуй (политика) политический принцип. Разделяй и властвуй (программирование) парадигма разработки алгоритмов. Разделяй и Властвуй (игра) компьютерная игра. Разделяй и властвуй / Divide And Conquer эпизод… … Википедия
Разделяй и властвуй! — Разделяй и властвуй: Разделяй и властвуй (политика) политический принцип. Разделяй и властвуй (программирование) парадигма разработки алгоритмов. Разделяй и Властвуй (игра) компьютерная игра. Разделяй и властвуй / Divide And Conquer эпизод… … Википедия
Разделяй и властвуй (информатика) — У этого термина существуют и другие значения, см. Разделяй и властвуй (значения). Разделяй и властвуй (англ. divide and conquer) в информатике важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи … Википедия
РиВ — Разделяй и властвуй: Разделяй и властвуй (политика) политический принцип. Разделяй и властвуй (программирование) парадигма разработки алгоритмов. Разделяй и Властвуй (игра) компьютерная игра. Разделяй и властвуй / Divide And Conquer эпизод… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Управление — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/30 августа 2012. Пока процесс обсуждения не завершён, статью можн … Википедия
Детектор затарков — (англ. Zatarc detector) вымышленное устройство в телесериале Звёздные врата SG 1, которое является очень эффективным детектором лжи. Ток ра используют детектор для проверки жертв манипуляции сознанием гоа’улдами затарков (спящих агентов,… … Википедия
Троичный поиск — (Тернарный поиск) это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой,… … Википедия
Технологии Ток\'ра в Звёздных вратах — Ток ра используют в основном технологии гоаулд. Это связан как с их физиологией, так и с характером их действий. Однако для выполнения спцифических задач они разрабатывают свои устройства и заимствуют технологии других например толланское… … Википедия
