트리 형식 데이터 구조의 런타임 이해

Question

각 부모가 자식 수를 무제한으로 가질 수 있고 트리의 최대 깊이가 4 인 트리 데이터 구조가 있습니다. 각 수준은 다른 클래스입니다.

내 친구가이 루프에 대한 구성되어 통과하는 알고리즘을 작성했습니다

의 psuedocode은 다음과 같습니다 :

root = tree.root(); 
for (int i = 0; i < root.children_size(); i++) 
    child1 = root.child(i); 
    for(int j = 0; j < child1.children_size(); j++) 
     child2 = child1.child(j); 
     for(int k = 0; k < child2.children_size(); k++) 
      child3 = child2.child(k); 

그는이 루프 3을 가지고 있기 때문에,이 알고리즘의 실행 시간은 O라고 주장 (n3). 제가 n이 무엇인지 물어볼 때, 그는 n이이 트리 내의 구조 여야하기 때문에 for 루프의 수는 의미가 없습니다. n은 트리의 전체 노드 수이고 실행 시간은 O (root.children_size + child1.children_size + child2.children_size)이므로이 알고리즘의 실행 시간은 O (n)입니다.

실행 시간에 대한 내 가정이 정확합니까, O (n)입니까, 아니면 O (n^3)입니까?

Answer 1

네가 맞습니다. 실제로 각 노드를 정확히 한 번 방문하면 (즉, dfs의 최악의 경우) depth first search을 고용하고 있기 때문에 복잡도는 O (N)입니다. 친구가 염려하는 한 깊이가 (n 여기서 for 루프의 수)는 고정되어 있습니다.

Answer 2

당신 말이 맞습니다. 모든 노드를 한 번 방문하면 O (N)이됩니다. 여기서 N은 전체 노드 번호입니다. 트리의 노드들.