[%] 모든 트리비교&업데이트 하는 연산이 왜 O(n^3)야?

[익명(180.71)]

https://reactjs.org/docs/reconciliation.html

여기 보면 한 트리에서 다른 트리로 transform하는 연산의 비용이 O(n^3)라 하는데

그냥 O(N)아니야? 중첩연산을 할 필요가 있는케이스가 있는건가?

[C++(rustisbetterthancpp)]

삽입할 때 N log N 인데 N log N이 N 번 반복되어서 N^3아닐까?

[C++(rustisbetterthancpp)]

생각해보니까 최악의 케이스네. 균형이진트리가 아닐 경우, 이전 트리를 순회해서 넣을 경우, 새로운 트리의 삽입 속도는 N^2이네

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(180.71)]

그럼 edit distance를 구하고 그걸 기반으로 수정하는거라서 그렇겠넹