Complexidade de algoritmo

[rregorr]

Considere o seguinte pseudocodigo, retirado de um livro:

Linear(A, n, x)
i = 1;
enquanto i <= n e x <> A[i] faça
i = i +1;
se i <= n
entao escreva(“encontrado”)
senao escreva(“nao encontrado”)

Com base nele, fiz o codigo java abaixo, que consiste em pesquisar se um número consta no vetor, retornando “encontrado” ou “não encontrado”, conforme o caso: Porem, so retorna a mensagem “encontrado!”, mesmo se o número a pesquisar não esteja no array. O q pode estar errado?

public class VerificaElemento {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	int[] A = { 100, 3, 0, 40 };
	int i = 1;
	int x = 1000;

	while (i <= A.length & x != A[i]) {
		i += 1;

		if (i <= A.length) {
			System.out.println("Encontrato!");
		} else {
			System.out.println("Não encontrado");
	}
}
}

}

Aproveito pra dizer q estou estudando complexidade de algoritmos, e gostaria de saber se alguem conhece algum plugin pra eclipse q ja me de a complexidade.

Grato.

[urbgames]

Olá rregorr. Primeiramente lhe recomendo uma literatura sobre análise de complexidade de algoritmos, não sei até que nível você deseja se aprofundar nesses estudos, mas de qualquer forma lhe recomendo o livro Introduction to Algorithms de Cormen (existe uma versão traduzida, mas tenha cuidado principalmente na segunda edição, pois existem alguns erros no livro). Lhe adianto que esse é um livro muito bom e bem “pesado” (tanto pela complexidade do assunto quanto pelas características físicas do livro ). Analisando rapidamente seu código diria que sob uma análise assintótica esse algoritmo é da ordem de O(n). Não conheço uma ferramente que faça isso no eclipse.

Sobre o código, se eu o entendi, a condição if e else deveria estar fora do while. Tenha cuidado ao transformar um pseudocódigo em código de uma determinada linguagem, pois vc precisa entender semanticamente o pseudocódigo e realizar as devidas adaptações à linguagem. Perceba que da forma que o algoritmo (java) está escrito ele nunca irá verificar a primeira posição (0) do array A. Verifica também o argumento i <= A.length, pois ele vai gerar um problema de ArrayIndexOutOfBoundsException, além de “furar” seu algoritmo quando for utilizado no if.