[Resolvido] "Medir" a eficiencia de um método de ordena

[gRoOvE 0]

Que aspectos devo levar em consideração para determinar que um método é melhor que outro? Por exemplo, tenho 500 registros e vou ordená-los usando Inserção Direta, Bubble Sort e Seleção Direta, devo levar em conta apenas o tempo de processamento?

 

Existe essa tal de complexidade, no método de Inserção é essa "O algoritmo de ordenação por inserção tem complexidade proporcional a n2 no pior caso, onde n é o número de elementos a serem ordenados.". Vejam se eu entendi, digamos que tenho 5 elementos, caso os cincos estejam ordenados de trás pra frente(pior caso acredito eu), terão que ser realizadas 25 trocas de posição entre os elementos?

[page_up 0]

Vou tentar explicar +/- como funciona:

 

para medir o nivel de complexidade de um algoritimo voce leva em conta o TEMPO, MEMORIA, ORDEM em que os algaritmos se encontram antes da ordenaçao...entre outros

 

entao por exemplo: em uma ordenaçao simples com um vetor de 5 elementos (voce quer botar eles em ordem crescente)

 

1º > o melhor caso seria o vetor ja se encontrar em ordem crescente entao ele é de complixidade O(logN).

2º > o pior caso seria o vetor em ordem inversa a crescente(maior pro menor), entao ele é de complexidade O(n), pois teria que "mecher" em todos os dados para concluir a tarefa.

 

 

dexa eu tentar com outro exemplo: uma busca

 

int buscaVet (tLvet *pv, int proc, int *pos)
{
	int i;
	for(i=0; i<pv->numElem; i++)
		if(pv->vet[i] == proc)
		{
			*pos = i; //achou, informa a posição
			return 1;
		}
		*pos = -1;
		return 0;
}

como realizar uma calculo basico de complexidade desse codigo ?

 

int i; =1

for(i=0;i<pv->numElem;i++) =n

if(pv->vet == proc) =n

*pos = i; =n

return 1; =n

*pos = -1; =1

return 0; =1

resultado = 4n

como nao faz muita diferença voce pode digamos "arredondar" para n, entao a complexidade seria O(n)

 

Abraço

[gRoOvE 0]

O que significa esse "O"? Tipo O(n) e O(logN). Não entendi teu exemplo. Andei lendo a respeito e deve se levar em consideração o número de comparações e trocas efetuadas até a ordenação desejada, certo? O que torna o algoritmo mais lento, a quantidade de comparações ou trocas?

[page_up 0]

O que significa esse "O"? Tipo O(n) e O(logN). Não entendi teu exemplo. Andei lendo a respeito e deve se levar em consideração o número de comparações e trocas efetuadas até a ordenação desejada, certo? O que torna o algoritmo mais lento, a quantidade de comparações ou trocas?

O(n) = algoritimo de complexidade n...O(logN) = algoritimo de complexidade logN

o termo O( ) é...digamos...uma forma de (nao é bem essa a palavra) declaração da complexidade

 

entao...o que você leu ta certo...mais você pode levar outros atributos em consideração tbm

é o seguinte vou te fazer uma pergunta...oque é melhor para um programa de busca ?

 

A -> uma busca que percorra todo o vetor comparando os valores

B -> uma busca que siga um determinado caminho...e no final você ache o mesmo termo, so que dessa vez com a metade das comparaçoes que a busca anterior fez

 

é para isso que serve a Analise de complexidade...você pega uma "busca" que tenha complexidade alta tipo O(n²) e tenta transformar ela numa busca de complexidade O(n)...não é o ideal ainda mias ja melhoro

 

e o que torna o algoritimo mais lento depende do codigo que você esta analizando:

se for uma BUSCA é a quantidade de comparações e se for uma ORDENAÇÃO é o numero de trocas realizadas

o mais normal(quer dizer estudado) é o caso da BUSCA...

 

Abraços

[gRoOvE 0]

Digamos que eu queira resolver esse O(n), como ficaria? LogN apenas? Sempre o que tiver dentro do paranteses será Log? Com certeza se for uma grande quantidade de registros, a Pesquisa Binária é mais eficiente...e trabalha de forma parecida com Métodos de Ordenação rápidos como o QuickSort, que procurar dividir o problema, e assim sucessivamente.

 

Como chegou ao resultado da complexidade O(4) no exemplo acima? Qual seria uma complexidade ideal para um algoritmo de pesquisa, por exemplo.

[//Coder 0]

esse é um conceito um pouco abstrato. nao tente pensar nele como uma função(como calcular O(4)) que eu acho que na verdade isso não interessa mt. a complexidade de um algoritmo é o quanto ele demora para ser executado com uma entrada de tamanho N. veja um exemplo prático.

queremos resolver um problema e temos duas soluções. uma com O(n) = n e outra com O(n) = 2^n .

A melhor escolha é a solução com o(n) = n. pois conforme n aumenta, o tempo de execução da primeira solução aumenta linearmente(O(n) = n) já a da segunda solução aumenta exponencialmente ( O(n) = 2^n ).

agora para comparação. com uma entrada n=1 a primeira da 1, e a segunda 2. os tempos de execução são parecidos.

já para uma entrada de 10. a primeira solução gasta 10 unidades de tempo e a segunda gasta 2^10.

uma TREMENDA diferença

---

Só complementando. O(n) é a complexidade no pior caso. a do melhor caso é dada por Ω(n) e a do caso médio por θ(n). e não necessáriamente são iguais. Como já foi dito. O pior caso não significa um n grande mas sim, por exemplo, um vetor totalmente desordenado.

Por exemplo. para um vetor com 10 posições já ordenadas a complexidade de um algoritmo de ordenação é Ω(n) = n. para um vetor totalmente desordenado é O(n) = n². isso quer dizer que, se eu der 10 entradas já ordenadas ele demora Ω(10)=10 unidades de tempo para executar e dizer: " ta tudo ordenado ". já se eu der o vetor totalmente desordenado(pior caso) ele demora O(10) = 100 unidades de tempo.

Para encontrar θ(n) em alguns casos é facil(se Ω(n) = O(n), obviamente θ(n) = Ω(n) = O(n)), já se Ω(n) != O(n) então depende de análise estatistica e talz. não é tao simples

[gRoOvE 0]

Esclareceu um pouco, vlw brother :D