|
|
|
|
|
|
by ajuc
4042 days ago
|
|
|
But you can just write for each cell the index of component it belongs to. It can't belong to many, right? 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. |
|
|
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.