Я должен согласиться, что это довольно странно, когда вы впервые видите алгоритм O (log n) ... откуда вообще этот логарифм? Однако оказывается, что есть несколько разных способов получить логический термин, который будет отображаться в нотации с большим 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 ⁱ 1

п 2 ^я

log ₂ n я

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

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

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

• Если массив пуст, верните, что элемента нет в массиве.
• Otherwise:
  • Look at the middle element of the array.
  • Если он равен искомому элементу, вернуть успех.
  • If it's greater than the element we're looking for:
    • Throw away the second half of the array.
    • Повторение
  • If it's less than the the element we're looking for:
    • Throw away the first half of the array.
    • Повторение

Например, чтобы найти 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 не может появиться в первой половине массива, поэтому мы можем выбросить первую половину массива, чтобы оставить

        5

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

        5
        ^

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

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

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

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

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

п 10 ^{k + 1} - 1

п + 1 10 ^{к + 1}

журнал ₁₀ (n + 1) k + 1

(log ₁₀ (n + 1)) - 1 тыс.

Отсюда мы получаем, что k приблизительно равен десятичному логарифму числа n. Другими словами, количество цифр в 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

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

       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) итераций. Многие сложные алгоритмы, такие как алгоритм кратчайших путей Габова или масштабируемая версия алгоритма максимального потока Форда-Фулкерсона, имеют логарифмический термин в их сложности потому что они работают по одной цифре за раз.

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

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

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

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

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

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

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

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

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

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

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

Вы начинаете с МЕДИАНЫ (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)

Термин 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
==> журнал (10 ^ d)> журнал (X)
==> d * журнал (10)> журнал (X)
== > d> log (X) // И журнал снова появляется ...
==> d = floor (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, вот как это выглядит ->

Перестановка элементов

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

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

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)

Использование log (a) + log (b) = log (a * б),

==> журнал (п!)

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

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

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

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

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

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

Теперь МЕДИАНА (X, p, q, Y, j + 1, k) разрежет четверку.

Вместо этого я предлагаю этот алгоритм, назовите его МЕДИАНА (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)
}