Re:PathFinding.js
by TheLoneWolfling on Thursday May 28, 2015 @01:30PM
(#9619686)
> I'm not sure we're talking about the same thing.
We are.
> But you can just write for each cell the index of component it belongs to. It can't belong to many, right?
Right. Each cell belongs to 1 and only 1 connected component.
However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance.
As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall.
In practice you can treat this as effectively O(n), however.
So you treat 1 integer as log n? That's very technical, but in that case OK.
Re:PathFinding.js
by TheLoneWolfling on Thursday May 28, 2015 @07:42PM
(#9621886)
Yes. Although, as I said, in practice you can treat the integer index as constant space.
So it is O(N) in space?
I'm not sure we're talking about the same thing. I mean space requirements for the results of preprocessing.
Preprocessign itself may require computing cluster for all I care.