about the calculation of time complexity, this article is very clear, and I suggest you read it carefully.

as to why the time complexity of traditional tree node comparison algorithm is O (n ^ 3) , while react's diff algorithm only needs O (n) , this is because react makes a lot of assumptions about tree node comparison, restricts a lot of things, and does not do too complex computing operations, so it reduces the complexity. While the traditional tree node needs to do a very complete check, such as comparing different levels of tree structure, it needs to be considered in the traditional algorithm, while react assumes that all the comparisons are carried out at the same level, which, of course, will greatly reduce the computational complexity.

, please refer to this article . I'm just a porter.

react trees are compared according to levels. He will give the tree the number 0meme1pl 2p3pl 4. Then compare with the same number. So the complexity is n, which is easy to understand.

the key is how to calculate the complexity of traditional diff? Traditional diff requires cross-level comparisons in addition to the above comparisons. He will compare the
nodes of two numbers, which is the complexity of n ^ 2. Then you need to edit the tree, which can occur at any node, and you need to traverse the tree again, so the complexity is n. It adds up to n ^ 3. I am not involved in the rigorous reasoning process here, just to give you a perceptual understanding. If there are any mistakes, we will not be held responsible.

here is an answer. You can also refer to react

how do you calculate O (n ^ 3) and O (n) from O (n ^ 3) to O (n),? -COIN's answer-Zhihu
https://www.zhihu.com/questio..