Анализ словаря

Question

Мой первый вопрос в анализе упоминается как

n + (n / 2) + (n / 4) + --- не более 2n. как мы получили результат как максимум 2n?

У нас есть коллекция массивов, где массив "i" имеет размер (от 2 до степени я). Каждый массив либо пуст, либо заполнен, и каждый отсортирован. Тем не мение, не будет никакой связи между элементами в разных массивах. Вопрос о том, какие массивы заполнены, а какие пустые, основан на двоичное представление числа элементов, которые мы храним.

Чтобы выполнить поиск, мы просто выполняем бинарный поиск в каждом занятом массиве. В в худшем случае это занимает время O (log (n) + log (n / 2) + log (n / 4) + .... + 1) = O (логарифм n).

Ниже приведен вопрос по фрагменту текста выше.

1. Как автор пришел с O (log (n) + log (n / 2) + log (n / 4) + .... + 1)?
2. и выше сумма равна O (логарифм n).

Спасибо!

Answer 1

n + n / 2 + n / 4 + n / 8 ... = n * (1/1 + 1/2 + 1/4 + 1/8 + ...)

сумма 1/1 + 1/2 + 1/4 + 1/8 + ... представляет собой геометрический ряд , который сходится к 2 , поэтому результат равен 2n.

.Автор говорит о коллекции массивов с размерами n, n / 2, n / 4, ..., и он выполняет бинарный поиск в каждом из них.Бинарный поиск в массиве с n элементами занимает O (log n) время, поэтому общее требуемое время равно O (log n + log n / 2 + log n/ 4 + ...) .