1
이는 숙제 질문이다 "노드 u 여부 노드 v의 조상입니까? "전처리 n 개의 * 로그를 사용하여 트리 (N) 알고리즘
실제로 나는 어떤 알고리즘도 O(log(n))보다 좋다고 생각하지 않습니다.
A
답변
0
O(n*log(n))에서 각 노드에 루트로 돌아가 자신의 조상 목록을 제공 할 수 있습니다. O(1)에서 노드는 "루트에서 얼마나 떨어져 있니?"라는 질문 중 하나에 대답 할 수 있습니다. "네 조상 중 누가 뿌리에서부터 거리 k인지?".
관련 문제
- 1. O (2^n * n) 배낭 알고리즘
- 2. 충돌 탐지를위한 O (n^log n) 알고리즘
- 3. n AVL 트리 합치기
- 4. O (N) 정렬 알고리즘
- 5. C++ n 트리 트리 라이브러리
- 6. 거리의 n * n 행렬에 대한 질문 알고리즘
- 7. 좌표를 얻는 N * N 여왕 알고리즘
- 8. n 차원 매칭 알고리즘
- 9. 다항식을 power n 알고리즘
- 10. O (n) 정렬 알고리즘
- 11. 2^n 복잡도 알고리즘
- 12. n 차원 보간법 C++ 알고리즘
- 13. n 점을 등거리에 배치하기위한 알고리즘
- 14. 의미의^\ n \ n \ n
- 15. 특정 알고리즘 정렬 N 소자
- 16. n x n 개의 문자 배열을 사용하여 세 방향으로 가능한 모든 문자열을 찾는 알고리즘?
- 17. tree.hh STL을 사용하여 n-ary 트리 채우기
- 18. N 개의 정렬되지 않은 그룹으로 부분 정렬하는 효율적인 알고리즘
- 19. 테이블에서 상위 N 개의 행 선택 N
- 20. n 트리 구현에 도움이 필요합니다.
- 21. n 개의 공백에있는 4 개의 객체의 순열에 대한 재귀 알고리즘
- 22. O (n log n) 시간에 특수 점 k를 찾는 알고리즘
- 23. Perl에 n- 트리 트리 구현이 있습니까?
- 24. 문자열을 사용하여 길이가 n 인 n 개의 높이가있는 사각형을 만듭니다.
- 25. 프로세스 트리 표시 N 초
- 26. n 트리 트리를 가로 질러
- 27. C 언어의 N 진 트리
- 28. 레일스 - escape_javascript가 없어도 \ n \ n \ n \ n \ n
- 29. O (fib n) 복잡도 알고리즘?
- 30. "\ n"
이것은 http://en.wikipedia.org/wiki/Lowest_common_ancestor의 특수한 사례이며 O (n) 전처리 후 시간 O (1)의 LCA를 찾는 알고리즘이 있음을 알 수 있습니다. 분명히, u는 LCA (u, v) = u이면 v의 조상입니다. – mcdowella