[Resolvido]Análise de complexidade em tempo de execução e classe de comportamento assintótico

Assuntos Gerais
#1

Bom, este é o meu 1º tópico no GUJ, não sei se postei no fórum de assunto certo, desculpem se for o caso, enfim:

Tenho um método que calcula a média entre N notas e estava querendo saber se fiz correto a Análise de complexidade em tempo de execução(melhor e pior caso) e determinar a classe de comportamento assintótico. Segue abaixo o trecho de código relevante ao cálculo(levando em contra atribuições, impressão, cálculos e testes como operação relevante). Deixo claro que não é exercício de faculdade, apenas ví esta classe(GradeBook, com pouquíssimas modificações) no livro do Deitel - Java como Programar 6ª edição, situada mais pro meio do cap. 4(não sei exatamente a página, não estou com o livro mais) e quis exercitar o assunto em questão que é de uma matéria passada:

[code] public void determineClassAverage() {

	Scanner s = new Scanner(System.in); //(1) melhor e pior caso  

	int total = 0; //(1) melhor e pior caso  
	int gradeCounter = 0; //(1) melhor e pior caso  
	int grade;  
	double average;  

	System.out.printf("Digite a %d nota(-1 sair): ", gradeCounter + 1); //(1) melhor e pior caso  
	grade = s.nextInt(); //(1) melhor e pior caso  

	while(grade != -1) { //(N + 1) pior caso ou (1) melhor caso  

		total += grade;  
		gradeCounter++;  

		System.out.printf("Digite a %d nota(-1 sair): ", gradeCounter + 1);  
		grade = s.nextInt();  
		//(4N) pior caso  
	}   

	if(gradeCounter != 0) { //(1) melhor e pior caso   

		average = (double)total / gradeCounter; //(1) pior caso  

		System.out.printf("\nMedia: %.1f", average); //(1) pior caso  
	}   

	else {  

		System.out.printf("Nenhuma nota foi inserida!"); //(1) melhor caso  
	}  
}[/code]

melhor caso: usuário digitar o valor de sentinela -1 de primeira:
Análise de complexidade: T(N) = 8
Classe de comportamento: O(1)

pior caso: usuário digitar N notas:
Análise de complexidade: T(N) = 5N + 9
Calsse de comportamento: O(N)

Está correto pessoal?
Obrigado.

#2

De acordo com as linha verdes de valor para cada sentença que vc colocou, esta correta sua análise.

Para o melhor caso ele roda em 8 linhas incluindo o teste do while, que ele faz para não entrar.
Para o pior caso N+1, porque ele sempre tem de executar o teste do -1 atoa para sair do laço e o restante basta somar, que vai dar 5n+9.

#3

Obrigado Max,
só estou na dúvida ainda se o melhor caso T(N) = 8 pertence à classe de comportamento assintótico O(1), já o pior caso T(N) = 5N + 9 acho que está certo, que pertence à Classe de comportamento O(N) mesmo.
Falou.

#4

Felipe,

Vc está correto.

Melhor caso O(1).
Pior caso O(n).

Geralmente quando tem 1 laço é O(n), 2 laços um dentro do outro O(n ao quadrado n2).

No site abaixo tem uns slides bakanas sobre isso.

http://www.slidefinder.net/a/analise_algoritmos_notação_assintótica/12848882/p2

#5

Resolvido!

#6