Złożoność znalezienia piku 2-D (MIT OCW 6.006)

W wideo recytacyjnym dla MIT OCW 6.006 o 43:30,

Biorąc pod uwagę $m \times n$ matryca $A$ z $m$ kolumny i $n$ wiersze, algorytm 2-D znajdowania pików, w którym pik jest dowolną wartością większą lub równą sąsiednim sąsiadom, opisano jako:

Uwaga: W przypadku nieporozumień przy opisywaniu kolumn za pomocą $n$Przepraszam, ale tak opisuje to wideo recytacyjne i starałem się zachować spójność z filmem. Bardzo mnie to zamieszało.

1. Wybierz środkową kolumnę $n/2$// Ma złożoność$\Theta(1)$

2. Znajdź maksymalną wartość kolumny $n/2$// Ma złożoność $\Theta(m)$ ponieważ są $m$ wiersze w kolumnie

3. Sprawdź poziom. sąsiedzi rzędu o maksymalnej wartości, jeśli jest większy, to znaleziono pik, w przeciwnym razie powtórz z$T(n/2, m)$// Ma złożoność$T(n/2,m)$

Następnie, aby ocenić rekurencję, mówi instruktor recytacji

$T(1,m) = \Theta(m)$ ponieważ znajduje maksymalną wartość

$$T(n,m) = \Theta(1) + \Theta(m) + T(n/2, m) \tag{E1}$$

Rozumiem następną część, o 52:09 w filmie, w której mówi on, aby leczyć $m$jak stała, ponieważ liczba wierszy nigdy się nie zmienia. Ale nie rozumiem, w jaki sposób prowadzi to do następującego produktu:

Myślę, że odtąd $m$ jest traktowany jak stała, dlatego jest traktowany jak $\Theta(1)$ i wyeliminowane w $(E1)$powyżej. Ale trudno mi się skakać$(E2)$. Czy to dlatego, że rozważamy teraz przypadek$T(n/2)$ ze stałą $m$?

Myślę, że „widzę” ogólny pomysł jest taki $\Theta(\log n)$operacja jest wykonywana, w najgorszym przypadku, dla m liczby rzędów. Próbuję wymyślić, jak opisać skok$(E1)$ do $(E2)$ komuś innemu, tzn. uzyskać prawdziwe zrozumienie.

Jak rozumiem, potrzeba $\Theta$(m) czas na ocenę wszystkich elementów w danej kolumnie i ustalenie, który z tych elementów jest globalnym maksimum. Gdzie$\Theta (\lg(n))$ przychodzi to, że w najgorszym przypadku algorytm musi ocenić $\lg(n)$kolumny w macierzy przed znalezieniem piku. Całkowita praca byłaby wtedy$\Theta(m\lg(n))$

Załóżmy na przykład, że macierz ma 32 kolumny i 8 wierszy.

1. Bierzesz środkową kolumnę, powiedzmy kolumnę 16. Oceniasz ją i okazuje się, że globalny pik kolumny jest zastąpiony przez element po prawej stronie. Upuszczasz kolumny 1-16 i skupiasz się na kolumnach 17-32
2. Znajdź środkową kolumnę pozostałej macierzy, którą jest kolumna 24, i oceniasz globalny pik (jest to ocena drugiej kolumny). Musisz przejść w prawo. Upuść kolumny 17–24, skup się na 25–32.
3. Znajdź środek (kolumna 28) - oceniasz (ocena trzeciej kolumny) i okazuje się, że musisz przejść w prawo. Upuść kolumny 25–28 i skup się na 29–32.
4. Oceń kolumnę 30 (czwarta ocena), znajdź, że musisz przejść w prawo, upuść kolumny 29-30.
5. Oceń jedną z pozostałych kolumn (ocena piątej kolumny) i gotowe.

W sumie ukończyłeś pięć ocen kolumn. 5 =$\lg(32)$ = $\lg(n)$ gdzie n jest liczbą kolumn w macierzy, a lg jest podstawą logarytmiczną 2.

analiza, którą zarysujesz, wydaje się niepoprawna. prawidłowa złożoność to$O(m)$ gdzie $m$to większy wymiar macierzy (wiersze lub kolumny). zobacz tę inną poprawną analizę, aby uzyskać więcej / więcej szczegółów. częścią błędu nie jest zdefiniowanie relacji powtarzalności$T(n,m)$ pod względem $T(n,m)$tylko (co jest poprawnie obsługiwane w papierze). artykuł pokazuje / używa nieskończonej serii:

$\begin{eqnarray*} T(n) & = & T \left({n \over 2}\right) + cn \\ T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\ &= & O(n) \end{eqnarray*}$