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

9

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×nAmn

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Θ(1)

  2. Encontre o valor máximo da coluna // Tem complexidade Θ ( m ) porque existem m linhas em uma colunan/2Θ(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)=Θ(m)

(E1)T(n,m)=Θ(1)+Θ(m)+T(n/2,m)

m

(E2)T(n,m)=Θ(m)Θ(logn)

mΘ(1)(E1)(E2)T(n/2)m

Θ(logn)(E1)(E2)

user52207
fonte

Respostas:

1

ΘΘ(lg(n))lg(n)Θ(mlg(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)

ManGI1
fonte
2

O(m)mT(n,m)T(n,m)

T(n)=T(n2)+cnT(n)=T(1)+cn(1+12+14+18+)=O(n)

vzn
fonte
11
Esta resposta está, de fato, fora de questão! O OP fala sobre o algoritmo no vídeo de recitação MIT OCW 6.006, enquanto esta resposta fala sobre um algoritmo diferente . Em particular, a análise descrita pelo OP está correta em relação ao algoritmo nesse vídeo.
John L.