작은 질문이 있습니다. AVL 트리가 있고이를 새 인스턴스에 1 : 1로 복사하려고합니다. 내가하는 일은 AVLTreeClass의 새 인스턴스를 만들고 등호 (C++ 11에서)로 복사 할 트리를 할당하는 것입니다.데이터 저장소 복사본을 새 인스턴스에 할당하는 시간 복잡도는 얼마나됩니까?
시간 복잡성에 대해 걱정해야합니까? 아니면 O (1)에서 실행됩니까?
도움 주셔서 감사합니다.
FunkyPeanut
이 완전히 구현에 의존하고 나는 사람이 확실한 대답을 줄 수 있다고 생각하지 않습니다 코드를 보지 않고있다. 그러나 O (1), O (n) 및 O (n log n)가 될 수있는 다양한 구현이 있습니다.
복사 생성자의 순진한 구현은 이전 트리의 모든 노드를 반복하고 공개 삽입 메소드를 호출하여 각 트리를 새 트리에 추가함으로써 작동합니다. 이것은 오래된 트리 요소 당 O (log n) 시간이 필요하므로 복잡성은 O (n log n)이됩니다. 그러나 이것은 특히 효율적이지 않습니다. 또 다른 방법은 맹목적으로 나무의 깊은 복사본을 만드는 것입니다. 이것은 트리 노드 당 O (1) 작업을 요구할 것이고 트리에 n 개의 노드가 있기 때문에 런타임은 O (n)이 될 것입니다. 다른 징후가 없다면 나는 당신의 런타임이 O (n)이고, 다른 프로그래머가 아닌 한 대부분의 프로그래머 (나는 믿는다)가 이것을 가정 할 것이라고 생각한다.
복사본이 일반적이지만 업데이트가 희박한 것으로 의심되는 경우 copy-on-write을 사용하여 복사본을 트리의 내부 표현으로 공유하고 원본 또는 복사 된 트리가 변경된 경우에만 전체, 전체 복사본을 공유하도록 할 수 있습니다 . 이렇게하면 복사본에 시간 O (1)이 발생하지만 변경 한 경우 O (n) 또는 O (n log n)의 비용이 발생합니다.
또는 persistent AVL 트리가있을 수 있습니다. 이 경우, 트리에서 돌연변이 연산은 O (log n) 시간에 실행되고 실제로 트리의 이전 버전을 손상시키지 않고 연산의 효과를 나타내는 새로운 트리를 생성합니다. 이 경우 삽입 및 삭제 작업에 대한 처벌을하지 않고 표현을 공유함으로써 O (1)에 사본을 만들 수 있습니다.
희망이 도움이됩니다.
그게 내가 알고 싶었던 것 이상이야! 고마워요 :) – FunkyPeanut
'시간 복잡성에 대해 걱정해야합니까? 아니면 O (1)에서 실행됩니까? '구현이 상상력에 맡겨지는 지 누가 알 수 있습니다. – 101010
흠 .. 일반적인 답변을 원했지만 ... 질문을 단순화하면 답할 수 있을까요? : 예를 들어 다음과 같은 데이터 구조를 복사하는 데 소요되는 시간은 얼마나됩니까? 배열의 새 인스턴스에 20 개의 항목이있는 표준 배열? – FunkyPeanut
아무도 모릅니다.하지만 O (n) 이외의 다른 노드에서 실행되도록하는 방법이 없다고 생각합니다. 각 노드를 정확히 한 번 복사해야합니다. 표준을 보지 못했지만, 복사본을 만드는 대신 나무를 쌓아 올리는 것을 매우 의심합니다. – AoeAoe