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

Question

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

Answer 1

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

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

1 = N / 2 ^x

умножить на 2 ^x :

2 ^x = N

теперь делайте журнал ₂ :

log ₂ (2 ^x ) = log ₂ Nx * log ₂ (2) = log ₂ Nx * 1 = log ₂ N

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

Answer 2

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

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

Здесь а = 1, б = 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

Answer 3

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

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

Укажите значение(n / 2) сверху, поэтому T (n) = T (n / 4) + 1 + 1.,,,T (n / 2 ^ k) + 1 + 1 + 1 ..... + 1

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

= T (1) + k

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

K = log n

Итак, сложность времени равна O (log n)

Answer 4

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

Answer 5

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

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

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

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

Answer 6

Вот Википедия Запись

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

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

Скажем, сначала у вас есть 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 ¹ + N / 2 ² + N / 2 ³ + ..... + N / 2 ^x … ..

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

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

В других случаях N / 2 ^x , где x такой, что 2 ^x

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

Answer 7

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

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

Answer 8

T (N) = T (N / 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) * ​​1009 *

Answer 9

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

1 = N / 2x

2x = N

Принимая log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

Answer 10

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

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

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

Это bi -нарный поиск, когда вы делите задачу на 2.

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

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