Бинарный поиск с рекурсивным вызовом и срезами: где спрятана линейная стоимость
Реализация бинарного поиска:
def search(a, x):
if not a:
return False
mid = len(a) // 2
if a[mid] == x:
return True
if a[mid] < x:
return search(a[mid + 1:], x)
return search(a[:mid], x)
Что верно про сложность этой функции?
- O(log n) времени и O(1) памяти: срез не копирует данные, а создаёт представление исходного списка
- O(n) времени и O(n) памяти: каждый срез копирует половину оставшегося списка, и сумма копирований линейна
- O(log n) времени и O(log n) памяти: время логарифмическое, лишняя память уходит только на кадры рекурсии
- O(n log n) времени: логарифмическое число уровней, и на каждом уровне копируется весь список целиком