[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
[grafos] O(n+m) x O(max{n,m})
- Subject: [grafos] O(n+m) x O(max{n,m})
- From: Jose Coelho de Pina <coelho@ime.usp.br>
- Date: Thu, 03 Apr 2003 10:26:33 -0300
Ois,
Quando escrevemos que as buscas em largura e profundidade
gastam tempo O(n+m) [linear], no fundo estamos escrevendo que
o consumo de tempo é O(max{n,m}), certo? Existem pessoas que
preferem escrever O(max{n,m}) a escrever O(n+m), isto é uma
questão de gosto.
Notem que, apesar dos grafos que imaginamos terem mais
arcos que vértices isto, em geral, não é verdade. Assim,
não podemos escrever que as buscas em largura e profundidade
gastam tempo O(m), já que para grafos (digamos) sem arcos o
consumo de tempo é O(n).
coelho