как рассчитать сложность бинарного поиска

144

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

Кролик кролик
источник
1
это может вам помочь: stackoverflow.com/a/13093274/550393
2cupsOfTech

Ответы:

385

Здесь более математический способ увидеть это, хотя и не очень сложно. ИМО намного понятнее, чем неформальные:

Вопрос в том, сколько раз вы можете разделить N на 2, пока не получите 1? По сути, это говорит о том, что бинарный поиск (половина элементов), пока вы не нашли его. В формуле это будет так:

1 = N / 2 x

умножить на 2 х :

2 х = N

Теперь сделайте журнал 2 :

log 2 (2 x ) = log 2 N
x * log 2 (2) = log 2 N
x * 1 = log 2 N

это означает, что вы можете разделить журнал N раз, пока у вас все не будет разделено. Это означает, что вы должны делить log N («выполнить бинарный поиск»), пока не найдете свой элемент.

duedl0r
источник
я только что вычислил его как t (n) = (2 ^ 2) * K. как сделать это в форме журнала?
Шан Хан
1
та же концепция объясняется графически: stackoverflow.com/a/13093274/550393
2cupsOfTech
Часть, которую я пропускаю: если у вас BST с 7 записями, какова его формула? log2 (7)? Я сделал расчет грубой силы с каждым возможным исходом и пришел к ответу, который не равнялся log2 (7), так что я делаю неправильно?
Перри Моншау
1
Намного проще, чем объяснение бинарного дерева.
NoName
1
Очень хороший ответ
VHS
22

Для двоичного поиска T (N) = T (N / 2) + O (1) // рекуррентное соотношение

Применить теорему Мастера для вычисления сложности времени выполнения рекуррентных соотношений: T (N) = aT (N / b) + f (N)

Здесь a = 1, b = 2 => log (база b) = 1

также здесь f (N) = n ^ c log ^ k (n) // k = 0 & c = log (основание b)

Итак, T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Источник: http://en.wikipedia.org/wiki/Master_theorem

abstractKarshit
источник
1
почему log (основание b) равно 1, когда a = 1 и b = 2, не должно ли быть 0?
Гауран Вьяс
16

Т (п) = Т (п / 2) + 1

T (n / 2) = T (n / 4) + 1 + 1

Поместите значение The (n / 2) выше, чтобы T (n) = T (n / 4) + 1 + 1. , , , Т (п / 2 ^ к) + 1 + 1 + 1 + 1 .....

= T (2 ^ k / 2 ^ k) + 1 + 1 .... + 1 до k

= Т (1) + K

Как мы взяли 2 ^ k = n

K = log n

Таким образом, сложность Времени O (log n)

Дирен Бирен
источник
10

Это не половина времени поиска, это не сделало бы это log (n). Это уменьшает это логарифмически. Задумайтесь об этом на мгновение. Если у вас 128 записей в таблице и вам нужно искать значение линейно, то, вероятно, потребуется около 64 записей в среднем, чтобы найти ваше значение. Это н / 2 или линейное время. При бинарном поиске вы устраняете 1/2 возможных записей на каждой итерации, так что самое большее потребуется всего 7 сравнений, чтобы найти ваше значение (логарифмическая база 2 из 128 равна 7 или 2, а степень 7 равна 128). сила бинарного поиска.

Майкл Дорган
источник
Извините за некропост, но 128 не является равномерно заполненным деревом. Я использовал базовый пример, чтобы обдумать это, и обнаружил, что 7 записей равномерно заполняют дерево тремя слоями. Я подсчитал, что сложность должна быть 17/7 (среднее от общей суммы сравнений), что составляет 2,43. Но log2 (7) составляет 2,81. Так чего мне здесь не хватает?
Перри Моншау
Два ответа - Первый здесь: даже если в математике нет ошибок, мы можем видеть, что среднее значение 2,43 все еще лучше, чем среднее значение 3,5 для линейного, и это низкое значение. Когда вы попадаете в сотни записей, log2 () становится намного лучше линейного. Я думаю, что вы видите это, хотя, так что дальше.
Майкл Дорган
1
Второй ответ: я не уверен, какое у вас дерево, где 7 уже заполнено. Когда я думаю о совершенном дереве из 8 записей, я вижу трехуровневое дерево с 8 листами. В этом дереве, независимо от того, какое число вы ищете, требуется всего 3 сравнения, чтобы перейти от корня к листу. Для 7 записей один из путей занял бы одно сравнение меньше, поэтому 20/7 (6 узлов из 3 сравнений, 1 узел из 2 сравнений), что составляет ~ 2,85. Log2 (7) составляет ~ 2,81. У меня нет математического фона, чтобы объяснить разницу в 0,04, но я думаю, что это связано с отсутствием дробных битов или какой-то другой магией :)
Майкл Дорган,
число есть количество листьев !? Не количество узлов? Это была большая часть информации, которую я упустил. Мне кажется странным, что функция основана на листьях, когда каждый ветвящийся узел также является потенциальной конечной точкой. Ну, в любом случае, спасибо, что поправил это для меня!
Перри Моншау
5

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

Это просто формальный математический жаргон для того, чтобы иметь возможность доказывать утверждения и т. Д. Он имеет очень простое объяснение. Когда n становится очень большим, функция log n будет увеличивать время, необходимое для выполнения функции. Размер «входного набора», n, это просто длина списка.

Проще говоря, причина бинарного поиска в O (log n) состоит в том, что он вдвое сокращает входной набор в каждой итерации. Проще думать об этом в обратной ситуации. На x итерациях, какой длинный список может проверить алгоритм двоичного поиска в max? Ответ 2 ^ х. Отсюда видно, что наоборот, в среднем алгоритму двоичного поиска требуется log2 n итераций для списка длины n.

Если, почему это O (log n), а не O (log2 n), то это потому, что, проще говоря, снова - Использование больших констант обозначений O не считается.

vidstige
источник
4

Вот запись в википедии

Если вы посмотрите на простой итеративный подход. Вы просто удаляете половину элементов для поиска, пока не найдете нужный элемент.

Вот объяснение того, как мы придумали формулу.

Скажем, сначала у вас есть N элементов, а затем в качестве первой попытки вы делаете «N / 2». Где N - сумма нижней границы и верхней границы. Первое значение времени N будет равно (L + H), где L - первый индекс (0), а H - последний индекс списка, который вы ищете. Если вам повезет, элемент, который вы попытаетесь найти, будет посередине [например, Вы ищете 18 в списке {16, 17, 18, 19, 20}, затем вычисляете ⌊ (0 + 4) / 2⌋ = 2, где 0 - нижняя граница (L - индекс первого элемента массива) и 4 - верхняя граница (H - индекс последнего элемента массива). В приведенном выше случае L = 0 и H = 4. Теперь 2 - это индекс найденного элемента 18, который вы ищете. Бинго! Ты нашел это.

Если бы случай был другим массивом {15,16,17,18,19}, но вы все еще искали 18, то вам не повезло, и вы бы сначала делали N / 2 (то есть ⌊ (0 + 4) / 2⌋ = 2 и затем поймите, что элемент 17 в индексе 2 - это не искомое число. Теперь вы знаете, что вам не нужно искать по крайней мере половину массива при следующей попытке поиска итеративным образом. усилия по поиску уменьшаются вдвое, так что, по сути, вы не ищите половину списка элементов, которые вы искали ранее, каждый раз, когда вы пытаетесь найти элемент, который вы не смогли найти в предыдущей попытке.

Так что худший случай будет

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 .....
т.е.:
N / 2 1 + N / 2 2 + N / 2 3 + ..... + N / 2 x … ..

пока ... вы не закончили поиск, где элемент, который вы пытаетесь найти, находится в конце списка.

Это показывает худший случай, когда вы достигаете N / 2 x, где x таков, что 2 x = N

В других случаях N / 2 x, где x таков, что 2 x <N Минимальное значение x может быть 1, что является наилучшим случаем.

Теперь, поскольку математически наихудший случай - это когда значение
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Более формально ⌊log 2 (N) + 1⌋

RajKon
источник
1
Как именно вы получаете более официальную версию?
Калле
Функция пола используется. Подробности в разделе производительности вики-ссылки ( en.wikipedia.org/wiki/Binary_search_algorithm ), предоставленной в ответе.
РаджКон
3

Log2 (n) - максимальное количество поисков, которое требуется, чтобы найти что-то в двоичном поиске. Средний случай включает в себя log2 (n) -1 поисков. Вот больше информации:

http://en.wikipedia.org/wiki/Binary_search#Performance

Джонатан М
источник
2

Допустим, итерация в бинарном поиске заканчивается после k итераций. На каждой итерации массив делится пополам. Итак, скажем, длина массива на любой итерации равна n На итерации 1,

Length of array = n

На итерации 2

Length of array = n⁄2

На итерации 3

Length of array = (n⁄2)⁄2 = n⁄22

Следовательно, после итерации k

Length of array = n⁄2k

Также мы знаем, что после k делений длина массива становится равной 1, поэтому

Length of array = n⁄2k = 1
=> n = 2k

Применение функции журнала с обеих сторон:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

Следовательно,

As (loga (a) = 1)
k = log2 (n)

Следовательно, временная сложность бинарного поиска

log2 (n)
SirPhemmiey
источник
1

Бинарный поиск работает путем разделения задачи пополам несколько раз, что-то вроде этого (подробности опущены):

Пример поиска 3 в [4,1,3,8,5]

  1. Заказать список товаров [1,3,4,5,8]
  2. Посмотрите на средний предмет (4),
    • Если это то, что вы ищете, остановитесь
    • Если это больше, посмотрите на первую половину
    • Если меньше, посмотри на вторую половину
  3. Повторите шаг 2 с новым списком [1, 3], найдите 3 и остановитесь

Это би -nary поиск , когда вы делите задачу 2.

Поиск требует только log2 (n) шагов, чтобы найти правильное значение.

Я бы порекомендовал Введение в алгоритмы, если вы хотите узнать об алгоритмической сложности.

Сайлас Паркер
источник
1

Поскольку мы сокращаем список вдвое каждый раз, нам просто нужно знать, сколько шагов мы получаем 1, так как мы продолжаем делить список на два. В приведенном ниже расчете x обозначает число раз, когда мы делим список, пока не получим один элемент (в худшем случае).

1 = N / 2x

2x = N

Принимая log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

Абдул Малик
источник
1

Т (Н) = Т (Н / 2) + 1

T (N) = T (N / 2) + 1 = (T (N / 4) + 1) + 1

...

T (N) = T (N / N) + (1 + 1 + 1 + ... + 1) = 1 + logN (база 2 log) = 1 + logN

Таким образом, временная сложность бинарного поиска составляет O (logN)

TizeeU0U
источник
0
ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.

2. at each iteration n is divided by half.

2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)

So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k 
k=log(N)  //base 2
Пиюш Джайн
источник
0

Позвольте мне упростить для всех вас пример.

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

1 2 3 4 5 6 ... 32

Предположим, что мы ищем 32. после первой итерации мы останемся с

17 18 19 20 .... 32

после второй итерации мы останемся с

25 26 27 28 .... 32

после третьей итерации мы останемся с

29 30 31 32

после четвертой итерации мы останемся с

31 32

На пятой итерации мы найдем значение 32.

Итак, если мы преобразуем это в математическое уравнение, мы получим

(32 X (1/2 5 )) = 1

=> n X (2 -k ) = 1

=> (2 k ) = n

=> k log 2 2 = log 2 n

=> k = log 2 n

Отсюда и доказательство.

Сумуха Х.С.
источник
0

Вот решение, использующее основную теорему, с читаемым LaTeX.

Для каждого повторения в отношении повторения для двоичного поиска мы преобразуем задачу в одну подзадачу со временем выполнения T (N / 2). Следовательно:

T (n) = T (n / 2) +1

Подставляя в основную теорему, получаем:

T (n) = aT (n / b) + f (n)

Теперь, поскольку logba0 и f (n) равно 1, мы можем использовать второй случай основной теоремы, потому что:

f (n) = O (1) = O (n0) = O (nlogba)

Это означает, что:

T (n) = O (nlogbalogn) = O (n0logn) = O (logn)

id01
источник