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

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

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

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

1 = N / 2 x

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

2 x = N

теперь выполните журнал 2 :

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

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

Для двоичного поиска 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

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

Т (п) = Т (п / 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) + к

Поскольку мы взяли 2 ^ k = n

K = log n

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

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

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

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

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

Вот вход в Википедию

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

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

Скажем, сначала у вас есть 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

Теперь, поскольку математически худший случай, когда значение
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⌋

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

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

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

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

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

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

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

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

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

1 = N / 2x

2x = N

Принимая log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

  • Добавление пути поиска заголовка системы к Xcode
  • Как построить BST при постоперационном обходе
  • Откат в звезде
  • Как искать таблицы Google?
  • Java - поиск файлов в каталоге
  • Быстрый алгоритм поиска подстрок в строке
  • Алгоритм поиска нескольких совпадений строк
  • Просмотр списка фильтров Android
  • Найти все элементы на странице, чей идентификатор элемента содержит определенный текст, используя jQuery
  • Android - Внедрение поискового фильтра в RecyclerView
  • Как я могу манипулировать значимостью поиска полнотекстового поиска MySQL, чтобы сделать одно поле более «ценным», чем другое?
  • Давайте будем гением компьютера.