MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Através da análise do algoritmo da função LCS-LENGTH abaixo, podemos afirmar que o tempo de execução e o espaço auxiliar requerido por este algoritimo são, respectivamente:

LCS-LENGTH(X,Y)
 m = X.length
 n = Y.length
 let c[0 ... MIN(m,n)] be a new table
 for i = 0 to MIN(m,n)
  c[i] = 0
 for i = 1 to MAX(m,n)
  previous = c[0]
  for j = 1 to MIN(m,n)
   if Xi == Yj
    c[j] = previous + 1
   else if c[j] >= c[j - 1]
    previous = c[j]
   else
    previous = c[j]
    c[j] = c[j - 1]
 return c[MIN(m,n)]

A) theta(m + n) e theta(m * n)

B) theta(m + n) e theta(MIN(m,n))

C) theta(m * n) e theta(m + n)

D) theta(m * n) e theta(MIN(m,n))

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade