Какова временная сложность скользящих и сгруппированных функций списка в scala

Question

Я использую скользящую функцию scala в списке, и после сверления она дает GroupedIterator.

Я брожу, какова временная сложность функций скольжения и группировки?

val list = (1 to 10).toList

list.iterator.grouped(3).foreach(println(_))
list.grouped(11).foreach(println(_))
val st = (1 to 7).iterator.grouped(3).withPartial(false).toList
st
list.sliding(3).foreach(println(_))
list.sliding(11).foreach(println(_))


list.sliding(3,2).foreach(println(_))
list.sliding(11,2).foreach(println(_))

Кажется, группировка занимает O (n), а скольжение занимает O (n * n).

Answer 1

Они оба O(n)

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

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