|
Oi, Nelson:
O finalzinho da resposta à pergunta 1b está assim no
gabarito: "O consumo de
tempo da função grau_saida é proporcional ao grau
de saída do vértice v".
Isto é apenas uma explicação, certo? Uma resposta
como "O(m)" estaria
correta (não digo no sentido de ser um limitante
superior, mas no sentido de
exatidão)?
Acho que não!
O(m) será da ordem do numero de arestas existentes no grafo inteiro.
Isso significa que O(m) será muito maior que O(grau de saida do vértice)
ou não no caso em que todas as arestas estão saindo daquele vértice.
Mas
de qualquer modo, o fato é que você pode, potencialmente, estar
pegando
muito mais coisas que o que você precisa. É como se você disse-se
que o
Quicksort é O(n^5). Isso é verdade? Bom, da definição da função O()
é
verdade pois o tempo do Quicksort está abaixo disso, mas a resposta
O Coelho até já
respondeu, mas meu ponto era em função do seguinte: eu sei
que O(m) seria o máximo possível, e portanto estaria correto do ponto de vista
"maximal" (assim como dizer O(m^2) ou algo assim). Mas é que, neste caso, em um
dado grafo, *todos* os arcos poderiam estar concentrados no mesmo vértice! É por
isso que eu achava mesmo que seria mais correto dizer que é O(m)... Afinal,
dizer que é O(grau-do-vértice) pode até ser mais exato, mas grau-do-vértice não
é dado do problema!
Um
abraço,
Rubens
P.S.: você mandou este email só para mim, e não para a lista, era isto
mesmo?
|