스칼라에서 슬라이스의 시간 복잡도 란 무엇입니까?

Question

스칼라 슬라이스 방법의 시간 복잡도 란 무엇입니까? O(m) 또는 O(n), 입니다. 여기서 m은 slice의 요소 수이고 n은 컬렉션의 요소 수입니다.

더 구체적인 질문 : 시간 복잡도는 someMap.slice(i, i + 1).keys.head이고, 여기서 i는 someMap.size보다 작은 임의의 정수입니다. 슬라이스 복잡도가 O(m) 인 경우 O(1)이어야합니다. 맞습니까?

Answer 1

이것은 분명히 기본 데이터 형식에 따라 다릅니다. 예를 들어 Array, ArrayBuffer, ByteBuffer 또는 IndexedSeqOptimized의 다른 하위 클래스를 자르는 것은 k 요소를 컨테이너에서 자르는 경우 O(k)입니다. 예를 들어, List은 으로 볼 수있는 O(n)입니다. 특정 유형의 출처를 확인하고 싶을 것입니다.

Map은 IterableLike에서 슬라이스 구현을 가져옵니다. 아래에 붙여 넣은 구현에서 컬렉션의 요소를 반복하는 비용과 새로 빌드 한지도를 만드는 데 드는 비용을 분명히 알 수 있습니다.

TreeMap의 경우 k 개 요소를지도에서 자르는 경우 O(n + k lg k)이어야합니다.

HashMap의 경우이 값은 O(n)이어야합니다.

override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = { 
    val lo = math.max(from, 0) 
    val elems = until - lo 
    val b = newBuilder 
    if (elems <= 0) b.result() 
    else { 
    b.sizeHintBounded(elems, this) 
    var i = 0 
    val it = iterator drop lo 
    while (i < elems && it.hasNext) { 
     b += it.next 
     i += 1 
    } 
    b.result() 
    } 
} 

의심스러운 경우 소스를 확인하십시오.