Мои знания о 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). [Подсказка: используйте концепции двоичного поиска]

Я должен согласиться, что это довольно странно, когда вы в первый раз видите алгоритм 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, мы получим

п / 2 ^я ≤ 1

п ≤ 2 ^я

журнал ₂ n ≤ я

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

Важная деталь заключается в том, что не имеет значения, на какую константу вы делите n (если она больше единицы); если разделить на константу k, потребуется log _k n шагов, чтобы достичь 1. Таким образом, любой алгоритм, который многократно делит входной размер на некоторую дробь, потребует 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 не может появиться в первой половине массива, поэтому мы можем выбросить первую половину массива, чтобы оставить

        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 ^{к + 1} - 1

п + 1 ≤ 10 ^{к + 1}

войти ₁₀ (п + 1) ≤ к + 1

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

Отсюда мы получаем, что 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.)

Другими словами, не думайте о мелких проблемах, где имеют значение «постоянные накладные расходы» на постановку проблемы, думайте о больших проблемах. И , когда речь идет о больших проблемах, большом-Oh (некоторая функция от 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
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // И появляется журнал снова ...
==> d = этаж (бревно (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 * b),

==> log (п!)

Это может быть приблизительно равно 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

Теперь 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)
}