Let's look at collections and see how complexity helps us to see how they will perform in different situations. We will look at commonly used collections and idioms.
The sliding method allows us to create a sliding window. Here's an example:
scala> val list = List(1,2,3,4,5,6) list: List[Int] = List(1, 2, 3, 4, 5, 6) scala> val list1 = list.sliding(2,1).toList list1: List[List[Int]] = List(List(1, 2), List(2, 3), List(3, 4), List(4, 5), List(5, 6))
This creates List[Int]
. Each element of List
contains the current element and its successor in the original list.
Here is the equivalent code in Clojure:
user=> (partition 2 1 '(1 2 3 4 5 6)) ((1 2) (2 3) (3 4) (4 5) (5 6))
It gives us similar results:
Let's see the complexity of this sliding window code. The time complexity is O(n). We need to visit each element of the original list twice: once when it is the first element, and second, when it is the second element. This is clearly...