Я смотрел вокруг stackoverflowНетривиальная Ленивая Оценка, которая привела меня к презентации Кигана Макаллистера:Зачем учить Хаскелл, На слайде 8 он показывает минимальную функцию, определяемую как:

minimum = head . sort

и утверждает, что его сложность O (n). Я не понимаю, почему сложность называется линейной, если сортировка по замене равна O (nlog n). Сортировка, упомянутая в посте, не может быть линейной, поскольку она не предполагает ничего о данных, как этого требуют методы линейной сортировки, такие как сортировка по счету.

Здесь ленивая оценка играет таинственную роль? Если да, то каково его объяснение?