Publicado em: 09/04/2009 23:18:44

Boas!

Estou a ter algumas duvidas em saber como determinar a ordem de complexidade em algoritmos e gostava de saber se alguem me poderia ajudar nesta minha duvida...

Portanto, tenho o seguinte algoritmo, para determinar se a soma de dois qq numeros de um vector sao iguais a 10:
public static void main(String[] args) { int[] vec = { 8, 3, 4, 1, 6, 5, 7 }; int k = 10; for (int i = 0; i < vec.length; i++) for (int j = i + 1; j < vec.length; j++) if (vec<i> + vec[j] == k) System.out.println(vec<i> + " : " + vec[j]); }
Segundo o q me foi explicado, este algoritmo teria ordem N^2.

Como faria para passar de O(N^2) para O(NlogN) ???

Obrigado e fikem bem,
[PT]Devilishly
_________________
PalcoPrincipal

Publicado em: 09/04/2009 23:18:44

Olá:

Repare que tanto o loop externo quanto o interno a iteração vai até o tamanho do array (chamemos de N). Portanto Este algorítmo seria de ordem quadrática ou O(N ^2).
Para passar de O(N ^2) para O(N * Log N) acho difícil. O que você pode fazer são algumas otimizações. Primeiro ordene seu array (usando Arrays.sort(int[]).
No loop externo você verifica se vec > k. Se for sai do loop externo, pois a partir daí todas as somas serão maior que k. No loop interno verifica se a soma vec + vec[j] é maior que k. Se for sai do loop interno pelo mesmo motivo acima.
O código ficaria assim:
public static void main(String[] args) { int[] vec = { 8, 3, 4, 1, 6, 5, 7 }; int k = 10; Arrays.sort(vec); for (int i = 0; i < vec.length; i++) if(vec<i> > k) { break; } for (int j = i + 1; j < vec.length; j++) int soma = vec<i> + vec[j]; if(soma > k) { break; } if (soma == k) System.out.println(vec<i> + " : " + vec[j]); }
O pior caso seria se todos os elementos de vec forem menor que k e todas as somas também forem menor que k. Neste caso, como consequência de ter que varrer todos os elementos do vetor, a ordem também será quadrática.

Grato,
_________________
Rafael U. C. Afonso
[i]Where is debug?
Debug is on the table[/i]