Komplexität der 2-D-Peakfindung (MIT OCW 6.006)

In einem Rezitationsvideo für MIT OCW 6.006 um 43:30 Uhr

Bei einer Matrix mit Spalten und Zeilen wurde der 2-D-Peakfindungsalgorithmus, bei dem ein Peak ein Wert ist, der größer oder gleich seinen benachbarten Nachbarn ist, wie folgt beschrieben:A m $m \times n$$A$$m$$n$

Hinweis: Wenn es Verwirrung bei der Beschreibung von Spalten über , entschuldige ich mich, aber so beschreibt es das Rezitationsvideo und ich habe versucht, mit dem Video übereinzustimmen. Es hat mich sehr verwirrt.$n$

1. Wählen Sie die mittlere Spalte // Hat KomplexitätΘ ( 1 )$n/2$$\Theta(1)$

2. Finden Sie den Maximalwert der Spalte // Hat Komplexität da eine Spalte Zeilen enthältΘ ( m ) m$n/2$$\Theta(m)$$m$

3. Überprüfen Sie den Horizont. Zeilennachbarn mit maximalem Wert, wenn er größer ist als ein Peak, wurde gefunden, andernfalls wird mit rekursiv // Hat die KomplexitätT ( n / 2 , m )$T(n/2, m)$$T(n/2,m)$

Um dann die Rekursion zu bewerten, sagt der Rezitationslehrer

$T(1,m) = \Theta(m)$ weil es den Maximalwert findet

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

Ich verstehe den nächsten Teil, um 52:09 im Video, wo er sagt, wie eine Konstante zu behandeln , da sich die Anzahl der Zeilen nie ändert. Aber ich verstehe nicht, wie das zu folgendem Produkt führt:$m$

Ich denke, da wie eine Konstante behandelt wird, wird es somit wie und in oben eliminiert . Aber es fällt mir schwer, zu springen . Liegt das daran, dass wir jetzt den Fall von mit einer Konstanten ?Θ ( 1 ) ( E 1 ) ( E 2 ) T ( n / 2 ) $m$$\Theta(1)$$(E1)$$(E2)$$T(n/2)$$m$

Ich denke, ich kann die Gesamtidee "sehen", dass eine -Operation im schlimmsten Fall für m Anzahl von Zeilen ausgeführt wird. Ich versuche herauszufinden, wie man den Sprung von nach zu jemand anderem beschreibt, dh wie man wirklich Verständnis gewinnt.$\Theta(\log n)$$(E1)$$(E2)$

Soweit ich weiß, dauert es (m) Zeit, um alle Elemente in einer bestimmten Spalte auszuwerten und zu ermitteln, welches dieser Elemente das globale Maximum ist. Wenn Θ ( lg ( n ) ) eintritt, muss der Algorithmus im schlimmsten Fall lg ( n ) -Spalten in der Matrix auswerten, bevor er einen Peak findet. Die Gesamtarbeit wäre dann Θ ( m lg ( n ) $\Theta$$\Theta (\lg(n))$$\lg(n)$$\Theta(m\lg(n))$

Angenommen, Ihre Matrix enthält 32 Spalten und 8 Zeilen.

1. Sie nehmen die mittlere Spalte, z. B. Spalte 16. Sie bewerten sie und stellen fest, dass der globale Peak der Spalte durch ein Element rechts ersetzt wird. Sie löschen die Spalten 1-16 und konzentrieren sich auf die Spalten 17-32
2. Suchen Sie die mittlere Spalte der verbleibenden Matrix, Spalte 24, und bewerten Sie einen globalen Peak (dies ist Ihre zweite Spaltenbewertung). Sie müssen sich nach rechts bewegen. Löschen Sie die Spalten 17-24 und konzentrieren Sie sich auf 25-32.
3. Finden Sie die Mitte (Spalte 28) - Sie bewerten (dritte Spalte Bewertung), und Sie finden, dass Sie nach rechts gehen müssen. Löschen Sie die Spalten 25 - 28 und konzentrieren Sie sich auf 29 - 32.
4. Bewerten Sie Spalte 30 (vierte Bewertung), stellen Sie fest, dass Sie nach rechts gehen müssen, und lassen Sie die Spalten 29-30 fallen.
5. Bewerten Sie eine der verbleibenden Spalten (fünfte Spaltenbewertung), und Sie sind fertig.

Insgesamt haben Sie fünf Spaltenauswertungen durchgeführt. 5 = = lg ( n ) wobei n die Anzahl der Spalten in der Matrix und lg die logarithmische Basis 2 ist.$\lg(32)$$\lg(n)$

$O(m)$$m$$T(n,m)$$T(n,m)$

$\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*}$