BFS糟糕的复杂性

问题描述 投票:0回答:2

我使用邻接列表来表示OCaml中的图形。然后我从节点s开始在OCaml中进行了以下BFS实现。

let bfs graph s=
    let size = Array.length graph in
    let seen = Array.make size false and next = [s] in 
    let rec aux  = function 
    |[] -> ()
    |t::q -> if not seen.(t) then  begin seen.(t) <- true;  aux (q@graph.(t)) end  else aux q 
    in aux next

size表示图的节点数。 seen是一个数组,其中seen.(t) = true如果我们看到节点tnext是我们需要看到的节点的列表。

通常情况下,BFS的时间复杂度通常是线性的(O(V + E)),但我觉得我的实现没有这种复杂性。如果我没有弄错的话,q@graph.(t)的复杂性非常大,因为它是O(| q |)。所以我的复杂性非常糟糕,因为在每个步骤中我都会连接两个列表,这很重要。

因此,我想知道如何调整此代码以实现高效的BFS?问题(我认为)来自使用列表实现队列。 OCaml中Queue模块的复杂性是否需要O(1)来添加元素?在这种情况下,我如何使用此模块使我的bfs工作,因为我不能像列表一样轻松地与Queue进行模式匹配?

time-complexity ocaml breadth-first-search
2个回答
0
投票

q @ graph的复杂性。(t)非常大,因为它是O(| q |)。所以我的复杂性非常糟糕,因为在每个步骤中我都会连接两个列表,这很重要。

你是绝对正确的 - 这是你的BFS的瓶颈。你应该很高兴能够使用Queue模块,因为根据https://ocaml.org/learn/tutorials/comparison_of_standard_containers.html插入和获取元素的操作是O(1)。

OCaml中队列和列表之间的区别之一是队列是可变结构,因此您需要使用非纯函数,如addtaketop,它们分别从前面插入元素,从前面弹出元素并返回第一个元素。


-1
投票

如果我没弄错的话,q @ graph。(t)的复杂性非常大,因为它是O(| q |)。

这确实是问题所在。你应该使用的是graph.(t) @ q。其复杂性为O(| graph。(t)|)。

你可能会问:这有什么不同?

区别在于| q |可以是从0到V * E的任何东西。图。(t)另一方面你可以使用。您最多访问一次图中的每个顶点一次,因此整体上会有复杂性

  O(\Sum_V |grahp.(v))

图中每个顶点的所有边的总和。换句话说:E。

这将带您了解O(V + E)的整体复杂性。

© www.soinside.com 2019 - 2024. All rights reserved.