Complexidade de localização de pico 2-D (MIT OCW 6.006)

Em um vídeo de recitação para o MIT OCW 6.006 às 43:30,

Dada uma matriz A com m colunas e n linhas, o algoritmo de localização de pico 2-D, em que um pico é qualquer valor maior ou igual a seus vizinhos adjacentes, foi descrito como:$m \times n$$A$$m$$n$

Nota: Se houver confusão na descrição de colunas via , peço desculpas, mas é assim que o vídeo de recitação o descreve e tentei ser consistente com o vídeo. Isso me confundiu muito.$n$

1. Escolha a coluna do meio // Possui complexidade Θ ( 1 )$n/2$$\Theta(1)$

2. Encontre o valor máximo da coluna // Tem complexidade Θ ( m ) porque existem m linhas em uma coluna$n/2$$\Theta(m)$$m$

3. Verifique horiz. vizinhos de linha de valor máximo, se for maior que um pico, foi encontrado; caso contrário, retorne com // Possui complexidade T ( n / 2 , m )$T(n/2, m)$$T(n/2,m)$

Então, para avaliar a recursão, o instrutor de recitação diz

$T(1,m) = \Theta(m)$

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

$m$

$m$$\Theta(1)$$(E1)$$(E2)$$T(n/2)$$m$

$\Theta(\log n)$$(E1)$$(E2)$

$\Theta$$\Theta (\lg(n))$$\lg(n)$$\Theta(m\lg(n))$

Por exemplo, digamos que sua matriz tenha 32 colunas e 8 linhas.

1. Você pega a coluna do meio, digamos a coluna 16. Você a avalia e descobre que o pico global da coluna é substituído por um elemento à direita. Você solta as colunas 1-16 e se concentra nas colunas 17-32
2. Localize a coluna do meio da matriz restante, que é a coluna 24, e você avalia um pico global (esta é sua segunda avaliação de coluna). Você acha que precisa se mover para a direita. Solte as colunas 17-24, concentre-se em 25-32.
3. Encontre o meio (coluna 28) - você avalia (avaliação da terceira coluna) e acha que precisa se mover para a direita. Solte as colunas 25 - 28 e concentre-se em 29 - 32.
4. Avalie a coluna 30 (quarta avaliação), descubra que você precisa mover para a direita e solte as colunas 29-30.
5. Avalie uma das colunas restantes (avaliação da quinta coluna) e pronto.

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