В массиве движется окно, нужно указать все максимумы на каждом движении окна.
Сделать это необходимо за время O(n) где n - длина массива.
Я в питоне новичок, а алгоритмы только учу, поэтому тяжело определить скорость.
Вопрос правильно ли я определил скорость? И соответствует ли второй алгоритм задаче?
Или первый?
Сделал сначала первый, но вроде как, в худшем случае будет искать максимумы в каждом окне, т.е. -медленно. Как улучшить?
def pushwindow(array, window):
"""
возвращает список из максимумов окна в массиве
худшая скорость квадрат логарифма размера окна
"""
if window==1: return array
results=[]
start = 0
end = window-1
len_array = len(array)
max_window = max(array[:window]) # находит максимум в первом окне
results.append(max_window)
while end < len_array-1: # работает пока окна в пределах массива
end+=1
if array[end]>=max_window: # делает новый максимум, если он
max_window = array[end] # больше предыдущего максимума
start+=1
elif max_window!=array[start]: # если текущий максимум не
start+=1 # является началом окна максимум
else: # не меняется
start+=1
max_window = max(array[start:end+1]) # ищет новый максимум в
results.append(max_window) # окне - плохо!!!
return results
Второй вроде лучше, но не уверен. Как его можно улучшить?
def pushwindow2(array, window):
"""
выводит максимумы при каждом движении окна
оценка скорости O(2array) не зависит от окна
"""
results = [array[0]]
for index, value in enumerate(array[1:]):
for index2, value2 in enumerate(results): # ставит новый элемент
if value2 <= value: # на место по возрастанию
results.insert(index2, value) # начиная от 0
break
else:
results.append(value) # или в конец
if len(results) == window: # должно вызывать только один раз
print (results[0]) # но проверяется на каждом цикле - плохо!!!
if len(results) == window+1:
results.remove(array[index-window+1]) # удаляет элемент из списка при
print (results[0]) # движении окна
Буду очень признателен за помощь
