зачем считать сложность времени бинарного поиска как log2N

Question

Может ли кто-нибудь объяснить мне, когда речь заходит о «двоичном» поиске, мы говорим, что сложность времени выполнения равна O (log n) ? Я искал это в Google и получил ниже,

"Количество раз, которое вы можете сократить пространство поиска вдвое, равно логу ₂ n".

Я знаю, что мы делим пополам, пока не найдем ключ поиска в структуре данных, но почему мы должны рассматривать его как log ₂ n ? Я понимаю, что e ^x - это экспоненциальный рост, и поэтому log ₂ n - это двоичный распад. Но я не могу интерпретировать бинарный поиск с точки зрения моего понимания определения логарифма.

Спасибо

Answer 1

Думайте об этом так:

Если вы можете позволить себе половину чего-то м раз (т.е. вы можете позволить себе тратить время, пропорциональное м ), то какой массив вы можете позволить себе искать?

Очевидно, массивы размером 2 ^м , верно?

Таким образом, если вы можете искать массив размером n = 2 ^m , то время, которое требуется, пропорционально m и решению m для n выглядит так:

n = 2 ^м

log ₂ (n) = log ₂ (2 ^m )

log ₂ (n) = м


Другими словами: выполнение двоичного поиска по массиву размером n = 2 ^m занимает время, пропорциональное m или, что эквивалентно, пропорциональное log ₂ (п) .

Answer 2

Двоичный поиск: -

давайте рассмотрим пример для решения проблемы.

предположим, что у нас «n» яблок, и каждый день половина яблок гниет.затем через сколько дней количество яблок будет равно 1.

первый день n яблок: аааа .... (всего n)

второй день: ааа а..а (всегоn / 2)

третий день: aaa .. a (всего n / (2 ^ 2));

так далее ..............давайте предположим, что через k дней количество оставшихся яблок будет 1
, т.е. n / (2 ^ k) должно стать 1 atlast

n / (2 ^ k) = 1;2 ^ к = п;применяя log к базе 2 с обеих сторон

k = log n;

таким же образом в бинарном поиске

сначала у нас осталось n элементов, затем n / 2, затемn / 4, затем n / 8, и так, наконец, у нас остался один элемент, поэтому сложность по времени равна log n