通俗的 diff 思路

大家好我是 132，昨天为了面试看了一下动态规划（虽然面试没考到），但还是有很多收获

反正不管怎么样，我只得出了一个结论，那就是，动态规划是用来解决 最xx 的问题的

很明显，diff 算法就是很典型的……最短编辑距离

diff 算法其实非常多，比较典型的主要有三种，一种是 preact 的试探下一个算法，一种是 snabbdom 的两端遍历的方法，再就是 inferno 的最长递增子序列的算法

前两种用于链表是在太过于困难，注意链表的特点，它不是数组，不能很方便地取到首尾节点，也不是递归，和递归时候的参数完全不同，所以两端遍历这种严重依赖首尾，索引的算法，用不到链表中

所以没办法只能用 inferno 的算法了，不过幸好，inferno 的算法似乎更简单

最长递增子序列

inferno 的算法，核心思想就是寻找一个最长递增子序列，然后这部分节点保持不动，其他的节点进行移动

举个例子

- A: [1 2 3 4] // 旧的
 - B: [4 1 2 4] // 新的
 - P: [3 0 1 2] // 索引队列
 - LIS: [0 1 2] // 最长递增子序列

我们只需要用一个数组记录变化后的索引队列，然后寻找这个索引队列的最长递增子序列

完美，然后就变成一个动态规划的问题了……

然后最终我们找到了最长递增子序列之后，这些就保持位置不动，然后其他的进行插入

即可

时间复杂度

大家可能会对时间复杂度有疑问，然后动态规划不是 O(n*) 吗，那 react 说的 O(n) 是咋回事

时间复杂度，是针对 js 代码的，也就是你写的代码是 O(n)，虽然 react 的代码时间复杂度低，但是它根本无法做到最短编辑距离呀

要想真正做到最短编辑距离，是不可能 O(n) 的，撑死就是优化动态规划，比如使用二分查找，让它变成 O(logn)

当然这些都不是重点，我们既然决定动这个算法，肯定要换个追求：

编辑距离 > 时间复杂度

总结

好吧，思路捋顺了，可是怎么实现哇呜呜呜

我得研究一下下了

Recommend