алгоритмы: как разделять-и-завоевать и сложность времени O (nlogn) связаны?

Question

В моих алгоритмах и структурах данных был введен класс divide-and-conquer algorithm, а именно merge sort.

При реализации алгоритма для задания мне пришло несколько вопросов.

1. ли какой-либо алгоритм, реализованный с использованием разделяй и властвуй парадигма имеет временную сложность O (NlogN)?

2. Это то, что часть рекурсии в подходе имеет способность уплотнять алгоритм, который работает как O (n^2) до O (nlogn)?

3. Что делает такой алгоритм в O (nlogn) первым.

Для (3) Я предполагаю, что это имеет какое-то отношение к деревьям рекурсии и возможному числу рекурсий. Может ли кто-нибудь, возможно, показать с помощью простого алгоритма разделения и покорения, который работает в O (nlogn), как вычисляется сложность?

Приветствия, Andrew

Answer 1

Я думаю, что все ответы на ваш вопрос может исходить от Master Theorem Это своего рода сказать вам, что бы ваши сложности практически для любого разделяй и властвуй решение у вас есть, и да, он должен делать все, с рекурсивными деревьями, играя с параметрами, вы обнаружите, что некоторые решения для разделения и завоевания не будут иметь сложность O (nlogn), на самом деле есть divide and conquer algorithms that have O(n) complexity.

Как раз в отношении вопроса 2, на самом деле не всегда можно найти некоторые проблемы, которые, как считается, невозможно решить быстрее, чем O (n^2), это зависит от характера проблемы.

Пример алгоритма, который работает в O (nlogn), и который, по моему мнению, имеет очень простой, понятный и образовательный анализ времени выполнения: MergeSort. Это можно понять со следующего рисунка:

Итак, каждый рекурсивный шаг вход разбивается на две части, тогда часть завоевания принимает O (n), поэтому каждый уровень дерева стоит O (n), сложный может быть, возможно, что количество рекурсивных уровней (высота дерева) - logn. Это более или менее просто. Поэтому на каждом шаге мы делим вход в 2 части n/2 элементов каждый и повторяем рекурсивно, пока мы не будем вводить постоянный размер. Поэтому на первом уровне мы делим n/2 на следующий n/4, затем n/8, пока не достигнем значения постоянного размера, который будет листом дерева, и последним рекурсивным шагом.

Итак, на i-м рекурсивном шаге мы делим n/2^i, поэтому дадим значение для i на последнем шаге. Нам нужно, чтобы n/2^i = O (1), это достигается при 2^i = cn для некоторой константы c, поэтому мы берем логарифм базы 2 с обеих сторон и получаем, что i = clogn. Таким образом, последним рекурсивным шагом будет clogn-th step, и, следовательно, дерево имеет clogn height.

Таким образом, общая стоимость MergeSort будет cn для каждого из уровней clogn recursive (tree), что дает сложность O (nlogn).

В целом вы можете быть уверены, что ваш алгоритм будет иметь сложность O (nlogn), если рекурсивный шаг имеет сложность O (n) и yo делятся на b проблем размера n/b или даже более общих , если части являются линейными частями n, которые суммируются до n. В другой ситуации очень вероятно, что у вас будет другое время выполнения.

Возвращаясь к вопросу 2, в случае QuickSort можно получить от O (n^2) до \ Theta (nlogn) именно потому, что средний случайный случай достигает хорошего раздела, хотя анализ времени выполнения еще сложнее, чем что.

Answer 2

Нет, разделяй и властвуй не гарантирует O (NlogN) производительность. Все зависит от того, как проблема упрощается при каждой рекурсии.

В алгоритме сортировки слияния исходная проблема делится на две половины. Затем выполняется операция O (n) по результатам. Вот откуда берется O (n ...).

Каждая из двух под-операций теперь имеет свой собственный n, который составляет половину от размера оригинала. Каждый раз, когда вы рекурсируете, вы снова делите проблему пополам. Это означает, что число рекурсий будет log2 (n). Вот откуда берется O (... logn).

Answer 3

Существует ли какой-либо алгоритм, реализованный с использованием парадигмы разделения и покорения, имеет временную сложность O (nlogn)?

В среднем Quicksort и Mergesort имеют временную сложность O (n log (n)), но это не всегда обязательно так. Big O Cheat Sheet

Является ли это, что рекурсия часть в подходе имеет право конденсироваться алгоритмом, который работает в как O (N^2) O (NlogN)?

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

Я настоятельно рекомендую это video где вы увидите, почему MergeSort is O (log (n)).

Что делает такой алгоритм в O (nlogn) в первую очередь.

Опять же, это только показатель того, сколько времени алгоритм потребляет по отношению к размеру ввода, так что, говоря, что алгоритм имеет временную сложность O (log (n)), не дает любая информация о том, как реализуется алгоритм, просто говорит, что когда начальный вход начинает увеличиваться, используемое время не будет увеличиваться прямо пропорционально, но вместо этого требуется больше времени и больше.

Answer 4

Имеет ли какой-либо алгоритм, реализованный с использованием парадигмы деления и покорения, имеет временную сложность O (nlogn)?

Нет, общая формула разделяй и властвуй является:

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

Что делает такой алгоритм в O (nlogn) первым?

Хороший пример логлинейного время сортировки слияние Алгоритм Построение м:

Является ли это, что рекурсия часть в подходе имеет право конденсироваться алгоритмом, который работает как O (n^2) до O (nlogn)?

Master теорема используется для определения время работы разделяй и властвуй алгоритмы

Если рецидив в этой форме

Тогда

Пример

Пусть

a = 2 
b = 4 
d = 1/2 

так 2 = 4^1/2 случай 2 применяется