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

Ответ 1

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

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

1 = N/2 ^x

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

2 ^x= N

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

Вот wikipedia entry

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

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

Говорите сначала, что у вас есть 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.....
i.e:
N/2 ¹ + N/2 ² + N/2 ³ +..... + N/2 ^x.....

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

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

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

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

Ответ 8

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

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

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

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

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

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

Ответ 9

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

1 = N/2x

2x = N

Принимая log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)

Ответ 10

Т (Н) = Т (Н /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)

Ответ 11

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

Ответ 12

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

Для простоты предположим, что в массиве есть 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 ⁵)) = 1

=> n X (2 ^-k) = 1

=> (2 ^k) = n

=> k log ₂ 2 = log ₂ n

=> k = log ₂ n

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

Ответ 13

Допустим, итерация в бинарном поиске заканчивается после 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)