kde jsou ti tipnci, co porád tvrdí, ze 4GB stačí každému? Asi staci, ale kdo se má srát s algoritmem kvuli trapným 2MB ram?

Problem totiz je - co vlastne chces, otazka je jestli to chces rychle nebo s ohledem na pamet, je mezitim jasnej trade-off.

Honza ma jednoznacne pravdu, ze muzes alokovat jen pole, které je nutné pro daný obrázek a pak ho zvětšovat dynamicky - a NE ROZHODNE to neovlivni slozitost (ne n krát, maximálně n logkrát a doví jestli).

Dalsi vec je, jak velky ten obrázek bude - kazdá barva jiná - 4000x4000+px, aby se alokovaly cele 2MB.
--
Dolni mez algoritmu (jak nejrychleji to asyptoticky teoreticky lze, omezeni daneho problemu) je dána výstupem a to je NxN a to jak pro paměti tak pro výpočetní složitost s tim nic neuděláš. A ty máš asyptoticky stejnou.
--

Pro specialni obtázky by se asi dal najít rychlejší algortmus, ale ne o moc.