kann zusammenhängende Regionen in einer Bitmap über O (r * c) verbessert werden?

Ich denke, die Verwirrung hier ist, dass Ihr Algorithmus tatsächlich in linearer Zeit und nicht in quadratischer Zeit läuft.

Bei Verwendung der Groß-O-Notation steht n für die Eingabegröße. Ihre Eingabe hier ist nicht nur r oder nur c , sondern r * c , da es sich um ein Gitter von Knoten handelt. Ihr Algorithmus läuft in O(r * c) , wie Sie in Ihrer Frage gesagt haben ... also läuft Ihr Algorithmus in O(n) , was eine lineare Zeit ist.

Es scheint mir, dass jeder Algorithmus, der dieses Problem löst, im schlimmsten Fall einmal jede Eingangszelle lesen muss. Die beste Laufzeit, auf die Sie hoffen können, ist O(n) . Wenn Ihr Algorithmus in O(n) ausgeführt wird, können Sie keinen Algorithmus verwenden, der im schlimmsten Fall schneller als der von Ihnen vorgeschlagene Algorithmus ausgeführt wird.

Ich kann mir ein paar clevere Tricks einfallen lassen. Wenn Sie beispielsweise einen Block von * s haben, könnten Sie in bestimmten Fällen nur die Diagonalen überprüfen. Das heißt, wenn Sie

Es spielt keine Rolle, ob Sie nur diese Zellen lesen:

Es sei denn, Sie haben zum Beispiel etwas in der unteren linken Ecke, in diesem Fall müssten Sie den unteren linken Teil von * lesen. Vielleicht kann Ihr Algorithmus in bestimmten Fällen schneller ausgeführt werden, aber für den schlimmsten Fall (was O measures ist) muss O(n) sein.

EDIT: Auch in dem Fall, in dem Sie nur die Hälfte der Knoten lesen, wäre die Laufzeit O(n/2) , die immer noch in der gleichen Reihenfolge ist ( O(n) ).

Dies steht in engem Zusammenhang mit Kennzeichnung von verbundenen Komponenten . Die Anzahl der angeschlossenen Komponenten ist nur ein Nebenprodukt der Beschriftung. Der im verlinkten Wikipedia-Artikel beschriebene Algorithmus funktioniert in linearer Zeit.

1. Erstellen Sie ein ungerichtetes Diagramm, in dem jeder Inselknoten mit seinen benachbarten Inselknoten verbunden ist.

2. Während es noch nicht besuchte Knoten gibt:

   • Wählen Sie einen noch nicht besuchten Knoten aus, führen Sie eine Tiefensuche durch und markieren Sie jeden besuchten Knoten, erhöhen Sie die Anzahl der Inseln.

3. Fertig.

Sowohl (1) als auch (2) benötigen O (n) Zeit.

Asymptotisch ist Ihr Ansatz das beste O (n).

Allerdings habe ich ein paar Dinge bemerkt:

Erstens:

Innerhalb der Funktion markVisited überprüfen Sie die Zellen in der folgenden Reihenfolge:

Eine bessere Reihenfolge wäre:

Dies wird im Cache besser abgespielt, da es beginnt, Werte direkt neben der aktuellen Position und sequentiell in einer bestimmten Zeile zu lesen.

(Beachten Sie, dass ausgehend von den Diagonalen eine größere Anzahl von Orten besucht wird, aber da die Überprüfung, ob eine Zelle besucht wurde, nur die letzte Prüfung ist, würde sie keine Zeit speichern).

Zweitens:

Im schlimmsten Fall eines Satellitenbildes, das nur Land enthält, wird Ihr Algorithmus jede Zelle mehrere Male besuchen (etwa einmal für jeden Nachbarn der Zelle).

Dies bedeutet, dass Sie ungefähr achtmal mehr Array-Zugriffe als möglicherweise benötigt.

Ich glaube, dass Sie dieses Problem mit einem mehr oder weniger linearen Durchlauf der Daten lösen können.

Ich denke gerade an einen Ansatz, wenn es funktioniert, füge ich den Code als Bearbeitung hinzu.

Ohne ein apriorisches Wissen über die Natur von Inseln kann der Algorithmus nicht effizienter als O (n) in der Zeit gemacht werden, jedoch kann der Algo-Speicher verbessert werden. Das besuchte Array ist einfach redundant. Hier ist ein kurzer Versuch (verzeihen Sie die Verwendung von ASCII artihmetics - nicht so lesbar, aber schneller zu codieren)