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

Question

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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