Сложность времени функции инициализации

Question

Я пытаюсь удалить последний элемент списка в Haskell и узнал о функции init.Поскольку функция, в которой я ее использую, должна быть O (n), я бы хотел знать, какова временная сложность init.

Answer 1

init :: [a] -> [a] это реализовано как [src] :

init [] =  errorEmptyList "init"
init (x:xs) =  init' x xs
  where init' _ [] = []
        init' y (z:zs) = y : init' z zs

Для генерациисписок, таким образом, он будет перебирать исходный список, каждый раз просматривая один элемент вперед и испуская предыдущий, учитывая, что хвост не является пустым списком.

Таким образом, это означает, что для списка n элементов, для вычисления init этого списка потребуется O (n) времени.

В вызовах функций на Haskell, однако, они ленивы.Например, если вы заинтересованы только в получении первых k элементов, он будет работать в O ( min ( n , k ) ) .