Numero:
Seja H=(V,E) um grafo não direcionado, representado por uma Matriz de Adjacência, onde existe apenas um caminho entre cada par (u,v) ∈ V, e as propriedades de um heap-máximo sejam verdadeiras.
Sobre o custo de implementarmos as funções pai(u) e raiz(H), é correto afirmar:
a. Se apenas acessássemos v ∈ V na diagonal superior de H, poderíamos em o(V) obter pai(u) e raiz(H).
b. Caso H seja transformado em uma Lista de Adjacência , ambas as funções terão custo O(V).
c. Se H fosse um grafo direcionado, o custo de pai(u) seria O(E).
d. Sendo O(depth) o custo de uma busca em profundidade em H, e O(root) o custo de raiz(H), para qualquer tamanho de V, root=Ω(depth) .
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
Nenhum comentário:
Postar um comentário