当通过将前向搜索中新生成的状态与后向搜索中所有生成的状态逐一比较来测试连接两个搜索时，给出双向搜索的时间复杂度。

回答：

如果你在每次迭代中解析给定集合中的所有n个节点或状态，那将是n乘以n，即n^2。

但是，如果你只解析到当前节点为止的所有节点，那么就是所有节点到n的总和。

所有节点到n的总和将是线性的，具体为1+2+3+…(n-1)+n = n(n+1)/2

我认为你的应用属于后者，实际上反过来理解会更好。考虑当前的前向节点在这个迭代中是n，(n-1)是第一个后向节点，(n-2)是第二个后向节点，以此类推，直到1，即最后一个后向节点：

N + (n-1) + (n-2) + … + 3 + 2 + 1 = n(n+1)/2

因此：

[a, b, c, d, e, f]1,a:  a,b,c,d,e,f2,b: a,b,c,d,e,f... 这将是n^2

而：

1,a:  []2,b: [a]3,c: [a,b]4,d: [a,b,c]..... 这将如上所述是线性的。