이진 트리의 InOrder 트리 순회의 시간 복잡도 O (n)?

public void iterativePreorder(Node root) { 
     Stack nodes = new Stack(); 
     nodes.push(root); 

     Node currentNode; 

     while (!nodes.isEmpty()) { 
       currentNode = nodes.pop(); 
       Node right = currentNode.right(); 
       if (right != null) { 
         nodes.push(right); 
       } 
       Node left = currentNode.left(); 
       if (left != null) { 
         nodes.push(left);  
       } 
       System.out.println("Node data: "+currentNode.data); 
     } 
}

출처 : 위키 트리 순회이진 트리의 InOrder 트리 순회의 시간 복잡도 O (n)?

는 O (n)이 될 것 시간의 복잡성인가? 재귀를 사용하면 시간 복잡도가 동일해질까요?

새로운 질문 :TreeA에서 노드를 찾기 위해 TreeA에서 특정 노드를 찾기 위해 위의 코드를 사용하면 TreeA만큼 많은 노드를 갖게됩니다. TreeB를 만드는 복잡성은 O (n^2) 그것은 n 노드이고 각 노드는 O (n) 인 위의 코드를 사용할 것이기 때문에? (검색 및 대부분의 다른 트리 작업과는 대조적으로) 이진 트리의 순회가 모든 트리 노드가 처리해야하기 때문에

출처

2012-03-11 Dan

예, 트리에서 N 개의 요소를 한 번 치기 때문에 그렇습니다. –

1. 새로운 질문을 별도로 게시하십시오. 2. 정확히 어떻게 TreeB가 만들어지기로되어 있는지 이해하지 못합니다 ... – thkala

모든 순회 알고리즘의 최소 복잡성은 O (N), 즉 선형 wrt 트리 내의 노드 수 그것은 누군가가 양자 컴퓨터 나 무언가를 만들지 않는 한 일반적으로 바뀌지 않는 불변의 사실입니다 ...

재귀의 경우 유일한 차이점은 호출 프레임을 푸시하여 암시 적으로 스택을 빌드한다는 것입니다 JVM 스택에, 샘플 코드는 스택을 명시 적으로 빌드합니다. 차라리 성능 차이를 추측하지는 않을 것입니다. 각 특정 유스 케이스 시나리오에 대해 두 가지 대안을 모두 프로파일 링하고 벤치마킹해야합니다.

출처

2012-03-11 20:48:14 thkala

이진 트리의 InOrder 트리 순회의 시간 복잡도 O (n)?

답변

관련 문제