[pacman-dev] [patch] patch IV rewritten for git

[Kevin Piche]

I got the O(N^2) from the edge computation.  If the package hierarchy
could be stored as a forest of trees or DAGs then the topo sort would be
O(N).  A straight tree/DAG implementation would be an interesting
project if I had the time.

k



On Tue, 2007-06-12 at 19:53 +0200, Xavier wrote:
> I also find recursive algorithm more natural for recursive structure.
> Maybe Nagy is the only one who doesn't :)
> But as far as I can tell, this is a correct implementation of the topo
> sort, so O(n+e) for the sort part. Did you also include the
> computation of the edges, which is O(n^2), or is there something else
> that I overlooked ?
> This was already observed by Nagy here :
> http://archlinux.org/pipermail/pacman-dev/2007-April/008135.html
> 
> Though when I first looked at this part, I find it odd, because O(n^2)
> shouldn't be needed there either, it's just a matter of :
> for t in targets do
>  for d in deps(t) do
>   add(d, t.children)
> But the problem is we don't have constant time access to the vertices.
> 
> _______________________________________________
> pacman-dev mailing list
> pacman-dev at archlinux.org
> http://archlinux.org/mailman/listinfo/pacman-dev