Powódź Wypełnij czterostronny algorytm złożoności - złożoność czasowa

„Szukałem, ale nie mogę znaleźć złożoności algorytmu wypełniania powodziowego (czterokierunkowy). Czym dokładnie jest złożoność notacji big O?

Odpowiedzi:

W najgorszym przypadku zostaną pokryte wszystkie komórki macierzy.

Pod względem czasu złożoności algorytm ten będziebyć równa rekurencyjnej: O (N × M) O (N × M), gdzie N i M są wymiarami macierzy wejściowej. Kluczową ideą jest to, że w obu algorytmach każdy węzeł jest przetwarzany najwyżej raz.

Sprawdź poniżej link, aby lepiej zrozumieć i więcej przypadków:

https://www.hackerearth.com/practice/algorithms/graphs/flood-fill-algorithm/tutorial/

Złożoność algorytmu zalewania jestproporcjonalna do liczby pikseli w wypełnionym obszarze. Więc jeśli masz np. kwadrat, a M jest liczbą pikseli na kwadracie, a N jest długością boku kwadratu, następnie M = N ^ 2, a złożoność to O (M) = O (N ^ 2).

Nawiasem mówiąc, na to pytanie już udzielono odpowiedzi w komentarzu w Stackoverflow. Widzieć Jak mogę poprawić wydajność mojej procedury zalewania?

Złożoność czasu to O (4 * mn) = (mn), ponieważ każda komórka macierzy jest przetwarzana co najwyżej 4 razy. Na przykład określona komórka może być wywoływana przez jej górną, dolną, lewą lub prawą komórkę.