Почему время выполнения алгоритма выбора O (n)?

Question

Согласно Википедии , алгоритм выбора имеет время выполнения O(n), но я не уверен в этом. Кто-нибудь может объяснить, почему это O(n)?

В обычной быстрой сортировке время выполнения равно O(n log n). Каждый раз, когда мы разделяем ветвь на две ветви (больше, чем стержень, и меньше, чем стержень), нам нужно продолжать обрабатывать обе стороны ветвей, тогда как Алгоритм выбора должен обрабатывать только одну сторона ветки. Я полностью понимаю эти моменты. Но если вы подумаете об алгоритме бинарного поиска, после того, как мы выбрали средний элемент, мы также продолжим поиск одна сторона ветви. Так что же делает алгоритм O(1)? Нет , конечно, алгоритм двоичного поиска по-прежнему O(log N) вместо O(1). Это то же самое, что и элемент поиска в бинарном дереве поиска. Мы ищем только одну сторону, но мы по-прежнему рассматриваем O(log n) вместо O(1).

Может кто-нибудь объяснить, почему в Алгоритме выбора, если мы продолжим поиск одной стороны, можно рассмотреть O(1) вместо O(log n)? Для меня я считаю алгоритм O(n log n), O(N) для разделения и O(log n) для количества раз, чтобы продолжить поиск.

Answer 1

Существует несколько различных алгоритмов выбора, от гораздо более простого быстрого выбора (ожидаемый O (n), наихудшего O (n ² )) до более сложного алгоритма медианы медиан (Θ (п)).Оба этих алгоритма работают, используя шаг разделения быстрой сортировки (время O (n)), чтобы переставить элементы и расположить один элемент в правильное положение.Если этот элемент находится в рассматриваемом индексе, мы закончили и можем просто вернуть этот элемент.В противном случае, мы определяем, на какой стороне продолжить и повторить.

Давайте теперь сделаем очень сильное предположение - предположим, что мы используем quickselect (выбираем стержень случайным образом) и на каждой итерации нам удается угадать точноесередина массива.В этом случае наш алгоритм будет работать следующим образом: мы делаем шаг разбиения, отбрасываем половину массива, а затем рекурсивно обрабатываем половину массива.Это означает, что при каждом рекурсивном вызове мы выполняем работу, пропорциональную длине массива на этом уровне, но эта длина продолжает уменьшаться в два раза на каждой итерации.Если мы разработаем математику (игнорируя постоянные факторы и т. Д.), Мы получим следующее время:

• Работа на первом уровне: n
• Работа после одного рекурсивного вызова:n / 2
• Работа после двух рекурсивных вызовов: n / 4
• Работа после трех рекурсивных вызовов: n / 8
• ...

Это означает, что общая выполненная работа определяется как

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 +1/4 + 1/8 + ...)

Обратите внимание, что этот последний член равен n раз сумме 1, 1/2, 1/4, 1/8 и т. Д. Если вывычислите эту бесконечную сумму, несмотря на то, что существует бесконечно много терминов, общая сумма равна 2. Это означает, что общая работа составляет

n + n / 2 + n / 4 + n/ 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n

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

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

Конечно, это очень оптимистичное предположение - мы почти никогда не получаем 50 /50 сплит!- но, используя более мощную версию этого анализа, вы можете сказать, что если вы можете гарантировать любое постоянное деление на множители, общая проделанная работа будет только некоторой постоянной величиной, кратной n.Если мы выберем абсолютно случайный элемент на каждой итерации (как мы делаем в быстром отборе), то в ожидании нам нужно выбрать только два элемента, прежде чем мы в конечном итоге выберем некоторый элемент разворота в середине 50% массива, что означает, что наожидание, только два раунда выбора точки разворота требуются прежде, чем мы закончим тем, что выбираем что-то, что дает 25/75 раскол.Вот откуда берется ожидаемое время выполнения O (n) для быстрого выбора.

Формальный анализ алгоритма медианы медиан намного сложнее, потому что рецидив трудно и не так просто проанализировать.Интуитивно понятно, что алгоритм работает, выполняя небольшой объем работы, чтобы гарантировать выбор хорошей точки разворота.Однако, поскольку сделано два разных рекурсивных вызова, анализ, подобный приведенному выше, не будет работать правильно.Вы можете использовать расширенный результат, называемый теоремой Акра-Бацци , или использовать формальное определение big-O, чтобы явным образом доказать, что время выполнения равно O (n).Для более подробного анализа ознакомьтесь с «Введение в алгоритмы, третье издание» Кормена, Лейссерсона, Ривеста и Стейна.

Надеюсь, это поможет!

Answer 2

Позвольте мне попытаться объяснить разницу между выбором и двоичным поиском.

Алгоритм двоичного поиска на каждом шаге выполняет O (1) операций.Всего существует log (N) шагов, и это делает его O (log (N))

Алгоритм выбора на каждом шаге выполняет O (n) операций.Но это 'n' продолжает уменьшаться вдвое каждый раз.Есть полностью log (N) шагов.Это делает его N + N / 2 + N / 4 + ... + 1 (log (N) раз) = 2N = O (N)

Для двоичного поиска это 1 + 1 + ...(log (N) раз) = O (logN) * ​​1007 *

Answer 3

В быстрой сортировке дерево рекурсии имеет уровни lg (N) и каждый из этих уровней требует O (N) объема работы.Таким образом, общее время выполнения составляет O (NlgN).

В Quickselect дерево рекурсивных проверок имеет глубину lg (N) уровней, и каждый уровень требует только половины работы уровня над ним.Это приводит к следующему:

N * (1/1 + 1/2 + 1/4 + 1/8 + ...)

или

N * Summation(1/i^2)
    1 < i <= lgN

Здесь важно отметить, что я иду от 1 до lGN, но не от 1 до N, а также не от 1до бесконечности.

Суммирование оценивается в 2. Следовательно, Quickselect = O (2N).

Answer 4

Потому что для выбора, вы не сортируете, обязательно. Вы можете просто посчитать, сколько существует предметов, имеющих какое-либо значение. Таким образом, медиана O (n) может быть выполнена путем подсчета того, сколько раз появляется каждое значение и выбора значения, которое имеет 50% элементов выше и ниже его. Это 1 проход через массив, просто увеличивая счетчик для каждого элемента в массиве, так что это O (n).

Например, если у вас есть массив «a» из 8-битных чисел, вы можете сделать следующее:

int histogram [ 256 ];
for (i = 0; i < 256; i++)
{
    histogram [ i ] = 0;
}
for (i = 0; i < numItems; i++)
{
    histogram [ a [ i ] ]++;
}
i = 0;
sum = 0;
while (sum < (numItems / 2))
{
    sum += histogram [ i ];
    i++;
}

В конце переменная «i» будет содержать 8-битное значение медианы. Было около 1,5 прохода через массив «а». Один раз через весь массив, чтобы посчитать значения, и еще раз через него, чтобы получить окончательное значение.

Answer 5

Сортировка = перестановка элементов - это O (n log n), но выбор - это что-то вроде взятия i-го элемента = индексация. И для этого и в связанном списке, или в двоичном дереве это O (n).

Answer 6

У быстрой сортировки нет больших значений nlogn - в худшем случае время выполнения равно n ^ 2.

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