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

Ответ 1

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

Что касается вопроса 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, поэтому дадим значение я для последнего шага. Нам нужно, чтобы n/2 ^ я = O (1), это достигается при 2 ^ я = cn для некоторой константы c, поэтому мы берем логарифм базы 2 с обеих сторон и получаем, что я = 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) именно потому, что средний случайный случай достигает хорошего раздела, хотя анализ времени выполнения еще более сложный.

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

Нет, общая формула разделения и покорения:

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

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

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

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

Основная теорема используется для определения времени выполнения алгоритмов разделения и покорения

Если повторение в этой форме

затем

пример

Пусть

a = 2
b = 4
d = 1/2

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