Пространственная сложность для подсчета количества вхождений в отсортированном массиве с использованием двоичного поиска

Мы знаем, что можем подсчитать количество вхождений в отсортированном массиве за время O(LogN) с помощью бинарного поиска [1,2].

[1] http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/

[2] Подсчитайте количество вхождений числа в отсортированном массиве

Какова пространственная сложность этого решения?


arrays sorting time-complexity space-complexity binary-search
person user2077168    schedule 07.11.2014    source источник
comment
Двоичный поиск в уже отсортированном непрерывном массиве элементов требует O(1) (или O(0)?) дополнительного пространства - вам просто нужна пара индексов/указателей, чтобы содержать ваш текущий диапазон поиска, и, возможно, пара дополнительных индексов/указателей, чтобы содержать ваш поиск результаты... Но, возможно, вы думаете о требованиях к пространству для сортировки или о чем-то еще? Если это так, вы могли бы быть немного более подробным, точно объясняя свой вопрос...   -  person twalberg    schedule 07.11.2014

Ответы (1)


arrow_upward
0
arrow_downward

Нет необходимости иметь дополнительное пространство. Достаточно нескольких переменных. (при условии, что массив уже отсортирован)

person Hengameh    schedule 22.07.2015