双向搜索的时间复杂度

Question

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

Answer 1

如果解析给定集合中的所有n个节点或状态，则在n个状态的每次迭代中，这将是n * n或n^2。

但是，如果您只解析每个节点直到当前节点，那么它是所有节点的总和，直到n。

多达n个的所有节点的总和将是线性的，特别是1 + 2 + 3 + ...（N-1）+ N = N（N + 1）/ 2

你的应用相信是后者，反过来可以更好地理解。 （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,f 
2,b: a,b,c,d,e,f 
... this would be n^2 

和：

1,a: [] 
2,b: [a] 
3,c: [a,b] 
4,d: [a,b,c] 
..... this would be linear as described above.