时间戳

首页 > 解决方案 > scala中列表的滑动和分组函数的时间复杂度是多少

scala - scala中列表的滑动和分组函数的时间复杂度是多少

问题描述

我在列表上使用 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)。

标签： scalascala-collections

解决方案

他们都O(n)

分组显然是O(n)因为它触及每个元素一次。

滑动也是O(n)因为它接触每个元素的次数是一个常数。它不止一次接触元素的事实不会影响复杂性。

推荐阅读