Что может привести к тому, что алгоритм будет иметь сложность O (log n)?

Question

Мои знания о big-O ограничены, и когда в уравнении появляются логарифмические выражения, это отбрасывает меня еще больше.

Может кто-нибудь объяснить мне в простых словах, что такое алгоритм O(log n)?Откуда взялся логарифм?

Это конкретно возникло, когда я пытался решить этот вопрос промежуточной практики:

Пусть X (1..n) и Y (1..n) содержит два списка целых чисел, каждый из которых отсортирован в порядке убывания.Дайте O (log n) -временной алгоритм, чтобы найти медиану (или n-е наименьшее целое число) всех 2n комбинированных элементов.Например, X = (4, 5, 7, 8, 9) и Y = (3, 5, 8, 9, 10), тогда 7 является медианой объединенного списка (3, 4, 5, 5, 7, 8, 8, 9, 9, 10).[Подсказка: используйте понятия бинарного поиска]

Answer 1

Я должен согласиться, что это довольно странно, когда вы впервые видите алгоритм O (log n) ... откуда вообще этот логарифм? Тем не менее, оказывается, что есть несколько разных способов, которыми вы можете получить лог-термин для отображения в нотации Big-O. Вот некоторые из них:

Многократное деление на постоянную

Возьмите любое число n; скажем, 16. Сколько раз вы можете разделить n на два, прежде чем получите число, меньшее или равное единице? Для 16 у нас есть

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Обратите внимание, что для этого нужно выполнить четыре шага. Интересно, что у нас также есть этот лог ₂ 16 = 4. Хммм ... как насчет 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Это заняло семь шагов, и log ₂ 128 = 7. Это совпадение? Нету! Для этого есть веская причина. Предположим, что мы разделим число n на 2 i раза. Тогда мы получим число n / 2 ⁱ . Если мы хотим найти значение i, где это значение не больше 1, мы получим

n / 2 ⁱ & le; 1

n & le; 2 ^я

log ₂ n & le; я

Другими словами, если мы выберем целое число i такое, что i & ge; log ₂ n, тогда после деления n пополам i мы получим значение, самое большее 1. Наименьшее i, для которого это гарантировано, примерно равно log ₂ n, так что если у нас есть алгоритм, который делит на 2, пока число не станет достаточно маленьким, то мы можем сказать, что оно заканчивается O (log n) шагов.

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

Так, где это происходит? Классическим примером является бинарный поиск , быстрый алгоритм поиска в отсортированном массиве по значению. Алгоритм работает так:

• Если массив пуст, вернуть, что элемент не присутствует в массиве.
• В противном случае:
  • Посмотрите на средний элемент массива.
  • Если он равен элементу, который мы ищем, верните успех.
  • Если он больше, чем искомый элемент:
    • Выбросьте вторую половину массива.
    • Повторите
  • Если он меньше, чем искомый элемент:
    • Выбросить первую половину массива.
    • Повторите

Например, для поиска 5 в массиве

1   3   5   7   9   11   13

Сначала мы посмотрим на средний элемент:

1   3   5   7   9   11   13
            ^

Поскольку 7> 5, а массив отсортирован, мы точно знаем, что число 5 не может быть в задней половине массива, поэтому мы можем просто отбросить его. Это оставляет

1   3   5

Итак, теперь мы посмотрим на средний элемент здесь:

1   3   5
    ^

Поскольку 3 <5, мы знаем, что 5 не может появиться в первой половине массива, поэтому мы можем выбросить первую половину массива, чтобы оставить </p>

        5

Снова посмотрим на середину этого массива:

        5
        ^

Поскольку это именно то число, которое мы ищем, мы можем сообщить, что 5 действительно находится в массиве.

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

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

Обработка значений по одной цифре за раз

Сколько цифр в числе оснований-10 n? Ну, если в числе есть k цифр, то у нас будет самая большая цифра, кратная 10 ^k . Наибольшее число k-цифр составляет 999 ... 9, k раз, и это равно 10 ^{k + 1} - 1. Следовательно, если мы знаем, что n имеет k цифр, то мы знаем что значение n не более 10 ^{k + 1} - 1. Если мы хотим решить для k в терминах n, мы получим

n & le; 10 ^{k + 1} - 1

n + 1 & le; 10 ^{к + 1}

log ₁₀ (n + 1) & le; к + 1

(log ₁₀ (n + 1)) - 1 & le; к

Из чего мы получаем, что k - это приблизительно логарифм от n по основанию-10. Другими словами, количество цифр в n равно O (log n).

Например, давайте подумаем о сложности добавления двух больших чисел, которые слишком велики, чтобы вписаться в машинное слово. Предположим, что у нас есть эти числа, представленные в базе 10, и мы будем называть числа m и n. Одним из способов их добавления является метод начальной школы - выведите числа по одной цифре за раз, затем работайте справа налево. Например, чтобы добавить 1337 и 2065, мы начнем с записи чисел как

    1  3  3  7
+   2  0  6  5
==============

Мы добавляем последнюю цифру и переносим 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Затем мы добавляем вторую (последнюю) цифру и переносим 1:

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

Затем мы добавляем третью к последней («антепоследней») цифру:

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

Наконец, мы добавляем четвертую к последней ("preantepenultimate" ... я люблю английский) цифру:

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

Теперь, сколько работы мы проделали? Мы выполняем всего O (1) работы на цифру (то есть постоянный объем работы), и есть O (max {log n, log m}) общее количество цифр, которые необходимо обработать. Это дает сложность O (max {log n, log m}), потому что нам нужно посетить каждую цифру в двух числах.

Многие алгоритмы получают термин O (log n), работая по одной цифре за раз в некоторой базе. Классическим примером является сортировка по основанию , которая сортирует целые числа по одной цифре за раз. Существует много разновидностей сортировки по основанию, но они обычно выполняются за время O (n log U), где U - максимально возможное целое число, которое сортируется. Причина этого заключается в том, что каждый проход сортировки занимает O (n) времени, и для обработки каждой из цифр O (log U) наибольшего отсортированного числа требуется всего O (log U) итераций. Многие продвинутые алгоритмы, такие как алгоритм кратчайших путей Габова или масштабируемая версия алгоритма максимального потока Форда-Фулкерсона , имеют логарифмический термин в своей сложности, поскольку работают с одной цифрой в время.

---

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

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

Answer 2

Когда мы говорим о больших-ой описаниях, мы обычно говорим о времени , которое требуется для решения проблем данного размера .И обычно для простых задач этот размер просто характеризуется количеством входных элементов, и это обычно называется n или N. (Очевидно, что это не всегда так - проблемы с графами часто характеризуются количеством вершин, V ичисло ребер, E; но сейчас мы поговорим о списках объектов, в списках которых имеется N объектов.)

Мы говорим, что проблема "является большой-о (некоторая функция из N)« тогда и только тогда, когда :

Для всех N> некоторого произвольного N_0 существует некоторая константа c, такая, что время выполнения алгоритма на меньше этой константыc раз (некоторая функция от N.)

Другими словами, не думайте о небольших проблемах, где «постоянные издержки» постановки задачи имеют значение, думайте о больших проблемах.И когда мы думаем о больших проблемах, big-Oh of (некоторая функция от N) означает, что время выполнения все еще всегда меньше, чем некоторое постоянное время этой функции.Всегда.

Короче говоря, эта функция является верхней границей с точностью до постоянного множителя.

Итак, «большой-ой log (n)» означает то же самое, что я сказал выше, за исключением того, что «некоторая функция N» заменена на «log (n)».

Итак, ваша проблема подсказывает вам подумать о бинарном поиске, так что давайте подумаем об этом.Предположим, у вас есть, скажем, список из N элементов, отсортированных по возрастанию.Вы хотите узнать, существует ли какое-либо заданное число в этом списке.Один из способов сделать то, что является , а не бинарным поиском, - просто отсканировать каждый элемент списка и посмотреть, является ли он вашим целевым номером.Возможно, вам повезет, и вы найдете это с первой попытки.Но в худшем случае вы будете проверять N раз.Это не бинарный поиск, и он не слишком большой - log (N), потому что нет никакого способа заставить его соответствовать критериям, которые мы набросали выше.

Вы можете выбрать эту произвольную константу равной c = 10, и если в вашем списке N = 32 элемента, все в порядке: 10 * log (32) = 50, что больше времени выполнения 32Но если N = 64, 10 * log (64) = 60, что меньше, чем время выполнения 64. Вы можете выбрать c = 100, или 1000, или gazillion, и вы все равно сможете найти Nэто нарушает это требование.Другими словами, N_0 отсутствует.

Если мы выполним бинарный поиск, мы выберем средний элемент и проведем сравнение.Затем мы выбрасываем половину чисел, и делаем это снова, и снова, и так далее.Если ваш N = 32, вы можете сделать это только около 5 раз, что является log (32).Если ваш N = 64, вы можете сделать это только около 6 раз и т. Д. Теперь вы можете выбрать эту произвольную константу c таким образом, чтобы требование всегда выполнялось для больших значений N.

При всей этой предыстории O (log (N)) обычно означает, что у вас есть какой-то способ сделать простую вещь, которая сокращает размер вашей проблемы вдвое.Так же, как бинарный поиск делает выше.Как только вы разрешили проблему пополам, вы можете снова разрезать ее пополам, и снова, и снова.Но, что важно, то, что вы не можете сделать, - это какой-то шаг предварительной обработки, который займет больше времени, чем O (log (N)).Так, например, вы не можете перемешать два своих списка в один большой список, если вы не можете найти способ сделать это и за время O (log (N)).

(ПРИМЕЧАНИЕ: почти всегда,Log (N) означает log-base-two, что я предполагаю выше.)

Answer 3

В следующем решении все строки с рекурсивным вызовом выполняются на половине заданных размеров подмассивов X и Y. Другие строки выполняются в постоянное время.Рекурсивная функция: T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).

Вы начинаете с MEDIAN (X, 1, n, Y, 1, n).

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)

Answer 4

Термин Log часто появляется при анализе сложности алгоритма.Вот некоторые объяснения:

1.Как вы представляете число?

Давайте возьмем число X = 245436. В этой записи «245436» содержится неявная информация.Сделав эту информацию явной:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^0

Что является десятичным расширением числа.Итак, минимальный объем информации , который мы должны представить для этого числа, составляет 6 цифр.Это не совпадение, поскольку любое число, меньшее 10 ^ d , может быть представлено в d цифр.

Так сколько цифр требуется для представления X?Это равно наибольшему показателю 10 в X плюс 1.

==> 10 ^ d> X==> log (10 ^ d)> log (X)==> d * log (10)> log (X)==> d> log (X) // И снова появляется log ...==> d = этаж (log (x)) + 1

Также обратите внимание, что это самый краткий способ обозначить число в этом диапазоне.Любое сокращение приведет к потере информации, поскольку отсутствующая цифра может быть сопоставлена ​​с 10 другими номерами.Например: 12 * можно сопоставить с 120, 121, 122,…, 129.

2.Как вы ищете число в (0, N - 1)?

Принимая N = 10 ^ d, мы используем наше самое важное наблюдение:

Минимумколичество информации для однозначной идентификации значения в диапазоне от 0 до N - 1 = log (N) цифр.

Это означает, что при запросе поиска числа в целой строкеот 0 до N - 1, нам нужно как минимум log (N) пытается найти его.Зачем?Любой алгоритм поиска должен будет выбирать одну цифру за другой при поиске номера.

Минимальное количество цифр, которое ему нужно выбрать, это log (N).Следовательно, минимальное количество операций, выполняемых для поиска числа в пространстве размера N, равно log (N).

Можете ли вы угадать сложности порядка двоичного поиска, троичного поиска или десятичного поиска?Его O (log (N))!

3.Как вы сортируете набор чисел?

Когда вас попросят отсортировать набор чисел A в массив B, вот как это выглядит ->

Permute Elements

Каждый элемент в исходном массиве должен быть сопоставлен с соответствующим индексом в отсортированном массиве.Итак, для первого элемента у нас есть n позиций.Чтобы правильно найти соответствующий индекс в этом диапазоне от 0 до n - 1, нам нужно ... log (n) операций.

Следующий элемент требует log (n-1) операций, следующий log (n-2)) и так далее.Итого получается:

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)Используя log (a) + log (b) = log (a * b),==> log (n!)

Это может быть приблизительно в nlog (n) - n.Это O (n * log (n))!

Следовательно, мы заключаем, что не может быть алгоритма сортировки, который мог бы работать лучше, чем O (n * log (n)).И некоторые алгоритмы, имеющие такую ​​сложность, являются популярными Merge Sort и Heap Sort!

Вот некоторые из причин, почему мы видим, что log (n) так часто всплывает в анализе сложности алгоритмов.То же самое можно распространить на двоичные числа.Я сделал видео об этом здесь. Почему log (n) появляется так часто при анализе сложности алгоритма?

Приветствия!

Answer 5

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

Answer 6

Пока не могу комментировать ... это некро!Ответ Ави Коэна неверный, попробуйте:

X = 1 3 4 5 8
Y = 2 5 6 7 9

Ни одно из условий не выполняется, поэтому MEDIAN (X, p, q, Y, j, k) обрежет обе пятерки.Это неубывающие последовательности, не все значения различны.

Также попробуйте этот пример четной длины с различными значениями:

X = 1 3 4 7
Y = 2 5 6 8

Теперь MEDIAN (X, p, q, Y, j +1, k) обрежет четыре.

Вместо этого я предлагаю этот алгоритм, вызовите его с помощью MEDIAN (1, n, 1, n):

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}