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

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

применить теорему мастера для вычисления сложности времени выполнения рекуррентных соотношений : Т(п) = в(н/б) + ф(Н)

здесь a = 1, b = 2 = > log (a base b) = 1

кроме того, здесь f (N) = n^c log^k(n) //k = 0 & c = log (a base b)

таким образом, Т(П) = О(П^С журнала^(К+1)н) = о(лог(Н))

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

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

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)

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

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

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

Если почему это является o(зарегистрируйте N), а не о(lоg2 н), это так просто раз поставил - через Большой о нотации константы не в счет.

здесь Википедия запись

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

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

скажем, изначально у вас есть 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
=> Регистрация₂(2^x) = журнал₂(N)
= > x * log₂(2) = log₂(N)
= > x * 1 = log₂(N)
= > Более формально log log₂(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 и остановите

Это bi-nary поиск при разделении задачи на 2.

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

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

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

1 = N / 2x

2x = N

принимая log2

log2(2x) = log2 (N)

x * log2(2) = log2 (N)

x = log2 (N)

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

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 + Фремонт, Калифорния (базовая 2 журнала) = 1 + Фремонт, Калифорния -

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