En un video de recitación para MIT OCW 6.006 a las 43:30,
Dada una matriz matriz con columnas y filas, el algoritmo de búsqueda de picos 2D, donde un pico es cualquier valor mayor o igual a sus vecinos adyacentes, se describió como:A m n
Nota: Si hay confusión al describir las columnas a través de , me disculpo, pero así es como lo describe el video de recitación y traté de ser coherente con el video. Me confundió mucho.
Elija la columna central // Tiene complejidadΘ ( 1 )
Encuentre el valor máximo de la columna // Tiene complejidad porque hay filas en una columnaΘ ( m ) m
Mira horiz. vecinos de fila de valor máximo, si es mayor, se ha encontrado un pico; de lo contrario, se repite con // Tiene complejidadT ( n / 2 , m )
Luego, para evaluar la recursividad, el instructor de recitación dice:
porque encuentra el valor máximo
Entiendo la siguiente parte, a las 52:09 en el video, donde dice que tratar a como una constante, ya que el número de filas nunca cambia. Pero no entiendo cómo eso lleva al siguiente producto:
Creo que, dado que se trata como una constante, se trata como y se elimina en anterior. Pero me está costando dar el salto a . ¿Es esto porque ahora estamos considerando el caso de con una constante ?Θ ( 1 ) ( E 1 ) ( E 2 ) T ( n / 2 ) m
Creo que puede "ver" la idea general es que se realiza una operación , en el peor de los casos, para m número de filas. Lo que intento descubrir es cómo describir el salto de a a otra persona, es decir, obtener una comprensión real.( E 1 ) ( E 2 )
fuente